Submission #535222

#TimeUsernameProblemLanguageResultExecution timeMemory
535222NaimSS007 (CEOI14_007)C++14
30 / 100
239 ms25520 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 d[N]; int vis[N]; int n,m; vi g[N]; vi dist(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; } set<int> S[N]; int32_t main(){ fastio; cin >> n >> m; int s,d,a,b; cin >> s >> d >> a >> b; assert(a!=b); while(m--){ int u,v; cin >> u >> v; if(v==a || v==b)S[u].insert(v); if(u==a || u==b)S[v].insert(u); g[u].pb(v); g[v].pb(u); } assert(sz(S[a])==1 && sz(S[b])==1); vi d1 = dist(s),d2=dist(d); int l = 0,r = n,ans = -1; dbg(d1[a],d2[a],d1[b],d2[b]); vi good; rep(i,1,n+1)if(sz(S[i]) == 2)good.pb(i); while(l<=r){ int m =(l+r)/2; int bom=0; if(d1[a]+m <= d2[a] && d1[a] + 1 + m <= d2[b])bom=1; swap(a,b); if(d1[a]+m <= d2[a] && d1[a] + 1 + m <= d2[b])bom=1; swap(a,b); for(auto to : good){ if(d1[to] + m < d2[a] && d1[to] + m < d2[b])bom = 1; } dbg(m,bom); if(bom){ ans = m; l = m+1; }else r=m-1; } cout << ans << endl; // math -> gcd it all // Did u check N=1? Did you switch N,M? }

Compilation message (stderr)

007.cpp: In function 'int32_t main()':
007.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
007.cpp:98:5: note: in expansion of macro 'dbg'
   98 |     dbg(d1[a],d2[a],d1[b],d2[b]);
      |     ^~~
007.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
007.cpp:111:7: note: in expansion of macro 'dbg'
  111 |       dbg(m,bom);
      |       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...