Submission #877286

#TimeUsernameProblemLanguageResultExecution timeMemory
877286mgl_diamondRigged Roads (NOI19_riggedroads)C++17
100 / 100
327 ms72776 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; #define foru(i, l, r) for(int i=(l); i<=(r); ++i) #define ford(i, l, r) for(int i=(l); i>=(r); --i) #define fore(x, v) for(auto &x : v) #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define fi first #define se second #define file "input" template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } void setIO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(file".inp", "r")) { freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } } const int N = 3e5+5, LOG = 19; int n, m, cur, id[N], par[N][LOG], high[N], up_w[N]; vector<ii> edges(1); vector<ii> adj[N]; bool spec[N]; struct dsu { int anc[N], up[N]; void reset() { foru(i, 1, max(n, m)) { anc[i] = -1; up[i] = i; } } int root(int u) { return anc[u] < 0 ? u : anc[u] = root(anc[u]); } void join(int u, int v) { if ((u = root(u)) == (v = root(v))) return; if (anc[u] > anc[v]) swap(u, v); anc[u] += anc[v]; if (high[up[u]] > high[up[v]]) up[u] = up[v]; anc[v] = u; } } comp, proc; void dfs_first(int u, int p) { foru(i, 1, LOG-1) { par[u][i] = par[par[u][i-1]][i-1]; } fore(x, adj[u]) { int v = x.fi, t = x.se; if (v == p) continue; up_w[v] = t; high[v] = high[u] + 1; par[v][0] = u; dfs_first(v, u); } } int lca(int u, int v) { if (high[u] < high[v]) swap(u, v); ford(i, LOG-1, 0) if (high[par[u][i]] >= high[v]) u = par[u][i]; if (u == v) return u; ford(i, LOG-1, 0) if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } return par[u][0]; } int main() { setIO(); cin >> n >> m; foru(i, 1, m) { int u, v; cin >> u >> v; edges.emplace_back(u, v); } foru(i, 1, n-1) { int e; cin >> e; spec[e] = 1; int u = edges[e].fi, v = edges[e].se; adj[u].emplace_back(v, e); adj[v].emplace_back(u, e); } high[0] = -1; dfs_first(1, 0); comp.reset(); proc.reset(); foru(i, 1, m) { if (id[i]) continue; int u = edges[i].fi, v = edges[i].se; if (!spec[i]) { int l = lca(u, v); vector<int> tmp; u = proc.up[proc.root(u)]; v = proc.up[proc.root(v)]; while (high[u] > high[l]) { if (!id[up_w[u]]) tmp.push_back(up_w[u]); proc.join(u, par[u][0]); u = proc.up[proc.root(u)]; } while (high[v] > high[l]) { if (!id[up_w[v]]) tmp.push_back(up_w[v]); proc.join(v, par[v][0]); v = proc.up[proc.root(v)]; } sort(all(tmp)); // fore(x, tmp) { // cout << x << " "; // } // cout << "\n"; fore(x, tmp) { id[x] = ++cur; } } id[i] = ++cur; } foru(i, 1, m) cout << id[i] << " "; }

Compilation message (stderr)

riggedroads.cpp: In function 'void setIO()':
riggedroads.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...