Submission #2631817

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

bool solve(int N,int M,vi& a, vi& b) {
    set<int> s1, sN;
    rep(i,M){
        int ai=a[i], bi=b[i];
        // if (ai>bi) swap(ai, bi);
        if (ai==1) s1.insert(bi);
        if (bi==N) sN.insert(ai);
    }
    vector<int> v(N);
    auto it = set_intersection(ALL(s1), ALL(sN), v.begin());
    return (it != v.begin());
}

int main() {
    int N, M; cin >> N >> M;
    vi a(M), b(M);
    rep(i,M) cin >> a[i] >> b[i];
    cout << (solve(N,M,a,b) ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Cat Snuke and a Voyage
User naoya_t
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1599 Byte
Status
Exec Time 181 ms
Memory 11904 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3
All 300 / 300 example0, example1, example2, example3, last0, last1, many0, many1, rand0, rand1, rand2
Case Name Status Exec Time Memory
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 640 KB
example3 1 ms 256 KB
last0 117 ms 2560 KB
last1 118 ms 2560 KB
many0 181 ms 11904 KB
many1 181 ms 11904 KB
rand0 76 ms 1920 KB
rand1 115 ms 2560 KB
rand2 67 ms 1792 KB