?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
55703452 |
Practice: praveenojha33 |
601A - 30 | C++17 (GCC 7-32) | Memory limit exceeded on test 57 | 249 ms | 262144 KB | 2019-06-18 09:15:51 | 2019-06-18 09:15:51 |
/*||>>>> Praveen Ojha <<<<>>>> 18 June 2019 <<<<>>>> 10:54:18 <<<<||*/ // #pragma GCC optimize("Ofast") //(Very Fast but Inaccurate) // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //(Small operations in many loops) // #pragma GCC optimize("unroll-loops") // #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define mod 1000000007 #define inf 1e18+5 #define sz(x) (int)x.size() #define PI 3.141592653589793238510 #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define vi vector<int> #define vpii vector<pair<int,int> > #define vvi vector<vector<int> > #define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " typedef long double ld; typedef pair<int,int> pii; //Read Problems Carefully & Check for corner cases N=0,1 ? /////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////////// const int N=500; vi rail[N],road[N]; int vis[N]; int rr[N][N]; int cnt,n,m; int bfs1(int uu){ queue <pii> qq; qq.push({uu,0}); while(!qq.empty()){ pii u=qq.front(); qq.pop(); vis[u.F]=1; if(u.F==n) return u.S; for(int v:rail[u.F]){ if(!vis[v]) qq.push({v,u.S+1}); } } return -1; } int bfs2(int uu){ queue <pii> qq; qq.push({uu,0}); while(!qq.empty()){ pii u=qq.front(); qq.pop(); // debug()<< imie(u); vis[u.F]=1; if(u.F==n) return u.S; for(int v:road[u.F]){ if(!vis[v]) qq.push({v,u.S+1}); } } return -1; } int32_t main(){__ int x,y; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>x>>y; rr[x][y]=rr[y][x]=1; rail[x].push_back(y); rail[y].push_back(x); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(!rr[i][j]){ road[i].push_back(j); road[j].push_back(i); } } } if(rr[1][n]){ cnt=bfs2(1); cout<<cnt<<"\n"; } else{ cnt=bfs1(1); cout<<cnt<<"\n"; } return 0; }
?
?
?
?