Submission #535247

#TimeUsernameProblemLanguageResultExecution timeMemory
535247NaimSS007 (CEOI14_007)C++14
100 / 100
232 ms16960 KiB
#include <bits/stdc++.h> #define ld long double #define endl "\n" #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb push_back #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define all(v) v.begin(),v.end() #define ff first #define ss second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end()); #define sz(v) ((int)v.size()) using namespace std; typedef vector<int> vi; #define y1 abacaba //#define left oooooopss #define db(x) cerr << #x <<" == "<<x << endl; #define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl; #define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<ll> vl; std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; } ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));} ll exp(ll b,ll e,ll m){ b%=m; ll ans = 1; for (; e; b = b * b % m, e /= 2) if (e & 1) ans = ans * b % m; return ans; } // debug: void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); } #ifdef LOCAL #define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl #else #define dbg(...) 42 #endif // const int N = 200100; int n,m; vi g[N]; vi dista(int a){ vector<int> d(n+2); rep(i,1,n+1)d[i] = 1e9; d[a] = 0; priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push(pii(d[a],a)); while(!pq.empty()){ auto t = pq.top();pq.pop(); if(t.ff != d[t.ss])continue; int v = t.ss; for(auto to : g[v])if(d[to] > d[v] + 1){ d[to] = d[v] + 1; pq.push(pii(d[to],to)); } } return d; } int s,d,a,b; vi d1,d2; int vis[N]; int getcommon(int ini){ rep(i,0,N)vis[i]=0; queue<int> q; q.push(ini); vis[ini] = 1; int res=0; while(!q.empty()){ int v = q.front(); q.pop(); res=max(res,d1[ini] - d1[v]); for(auto to : g[v]) if(!vis[to] && d1[to] == d1[v] - 1 && d2[to] == d2[v] - 1){ vis[to]=1;q.push(to); } } return res; } int32_t main(){ fastio; cin >> n >> m; cin >> s >> d >> a >> b; assert(a!=b); while(m--){ int u,v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } d1 = dista(a),d2=dista(b); int A = d1[d] - d1[s]; int B = d2[d] - d2[s]; if(A!=B){ cout << max(min(A,B),-1) << endl; }else{ cout << max(A - ((A + getcommon(s) < getcommon(d)) ? 1 : 0),-1) << endl; } // math -> gcd it all // Did u check N=1? Did you switch N,M? }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...