Submission #2631807

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(N), b(N);
    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 0
Code Size 1596 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3
All 0 / 300 example0, example1, example2, example3, last0, last1, many0, many1, rand0, rand1, rand2
Case Name Status Exec Time Memory
example0 2 ms 384 KB
example1 1 ms 256 KB
example2 2 ms 1408 KB
example3 1 ms 256 KB
last0 118 ms 2560 KB
last1 118 ms 2560 KB
many0 183 ms 11904 KB
many1 182 ms 11904 KB
rand0 77 ms 2304 KB
rand1
rand2 68 ms 2304 KB