Submission #266464

#TimeUsernameProblemLanguageResultExecution timeMemory
266464sealnot123Roller Coaster Railroad (IOI16_railroad)C++14
0 / 100
135 ms26344 KiB
#include "railroad.h" #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() #define FOR(i, a, b) for(int i=(a); i<=(b); ++i) #define ROF(i, a, b) for(int i=(a); i>=(b); --i) #define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin()) using namespace std; typedef pair<int,int> PII; typedef long long LL; typedef double DD; typedef long double LD; typedef pair<LL,LL> PLL; typedef pair<DD,DD> PDD; typedef vector<int> VI; typedef vector<LL> VL; const int N = 200004; int n; vector<int> mark, comp, dp, g[N]; queue<int> bfs; LL plan_roller_coaster(VI s, VI t) { int n = SZ(s); FOR(i,0,n-1) comp.pb(s[i]), comp.pb(t[i]); comp.pb(0); comp.pb(1e9+2); make_unique(comp); int m = SZ(comp); dp.resize(m, 0); mark.resize(m, 0); FOR(i,0,n-1){ s[i] = lower_bound(all(comp), s[i])-comp.begin(); t[i] = lower_bound(all(comp), t[i])-comp.begin(); if(s[i] == t[i]) continue; dp[s[i]]++; dp[t[i]]--; g[s[i]].pb(t[i]); } --dp[1]; g[0].pb(1); FOR(i, 1, m-2){ if(dp[i] > 0) return 1; while(dp[i] < 0) g[i].pb(i+1), ++dp[i], --dp[i+1]; } // check if the same component bfs.push(0); int cnt = 0; while(!bfs.empty()){ int u = bfs.front(); ++cnt; bfs.pop(); for(int e : g[u]){ if(mark[e]) continue; mark[e] = 1; bfs.push(e); } } if(cnt == m) return 0; return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...