Submission #333123

#TimeUsernameProblemLanguageResultExecution timeMemory
333123guka415Rigged Roads (NOI19_riggedroads)C++14
39 / 100
769 ms262148 KiB
#define fast ios::sync_with_stdio(false); cin.tie(0) #define foru(i, k, n) for (int i = k; i < n; i++) #define ford(i, k, n) for (int i = k; i >= n; i--) #define pb push_back #define mp make_pair #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <bitset> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> struct rmq { vector<vector<T>> a; vector<int> logs; int dep, len; rmq(vector<T> arr) { len = arr.size(); dep = 0; int tmp = len; while (tmp) { tmp >>= 1; dep++; } a.resize(dep); foru(i, 0, dep) { a[i].resize(len); for (int j = 0; j + (1 << i) <= len; j++) { if (!i)a[i][j] = arr[j]; else a[i][j] = min(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]); } } initLogs(); } void initLogs() { logs.resize(len + 1); logs[1] = 0; foru(i, 2, len + 1)logs[i] = logs[i >> 1] + 1; } T query(int l, int r) { int mylen = logs[r - l + 1]; return min(a[mylen][l], a[mylen][r - (1 << mylen) + 1]); } }; struct lca { vector<vector<int>> adj; vector<int> appear; vector<pii> dep; rmq<pii>* tree; int sz; lca(vector<vector<int>> adjacency) { adj = adjacency; sz = adjacency.size(); appear.resize(sz); dfsscan(0, -1, 0); tree = new rmq<pii>(dep); } void dfsscan(int src, int prev, int currdep) { appear[src] = dep.size(); dep.pb(mp(currdep, src)); for (auto x : adj[src]) { if (x == prev)continue; dfsscan(x, src, currdep + 1); dep.pb(mp(currdep, src)); } } int query(int a, int b) { int x = min(appear[a], appear[b]), y = max(appear[a], appear[b]); return tree->query(x, y).second; } }; const int sz = 5e5 + 5; vector<pii> adj[sz]; vector<pii> e; bitset<sz> good, done; int n, m; pair<pii, int> ft[sz]; int dep[sz]; lca* tre; set<int> toAdd; void dfsf(int src, int prv) { if (prv != -1) dep[src] = dep[prv] + 1; for (pii x : adj[src]) { if (x.first != prv) { ft[x.first] = { {src,1},x.second }; dfsf(x.first, src); } } } void input() { cin >> n >> m; vector<vector<int>> adja(n); foru(i, 0, m) { int a, b; cin >> a >> b; a--; b--; e.pb({ a,b }); } foru(i, 0, n - 1) { int pos; cin >> pos; pos--; int a = e[pos].first, b = e[pos].second; good[pos] = 1; adj[a].pb({ b,pos }); adj[b].pb({ a,pos}); adja[a].pb(b); adja[b].pb(a); } tre = new lca(adja); } int goUp(int src, int upto) { if (dep[src] <= dep[upto])return src; else { if (ft[src].first.second && !done[ft[src].second])toAdd.insert(ft[src].second); int ret = goUp(ft[src].first.first, upto); ft[src] = { { ret,0 },-1 }; return ret; } } void calcToAdd(int le, int ri) { toAdd.clear(); int f = tre->query(le, ri); ft[le] = { {goUp(le,f),0},-1 }; ft[ri] = { {goUp(ri,f),0},-1 }; } int main() { fast; input(); dfsf(0, -1); vector<int> ret(m); int crt = 1; foru(i, 0, m) { if (done[i])continue; else if (good[i]) { ret[i] = crt++; done[i] = 1; } else { int l = e[i].first, r = e[i].second; calcToAdd(l, r); for (int r : toAdd) { ret[r] = crt++; done[r] = 1; } ret[i] = crt++; done[i] = 1; } } foru(i, 0, m)cout << ret[i] << ' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...