Submission #877183

#TimeUsernameProblemLanguageResultExecution timeMemory
877183lognRigged Roads (NOI19_riggedroads)C++14
58 / 100
2060 ms52640 KiB
#include <bits/stdc++.h> //Logm using namespace std; #define int long long #define II pair<int,int> #define fi first #define se second const int N = 3e5+5; int n, m; II e[N]; int idx[N]; bool spec[N]; int par[N], rak[N]; void init(int n) { for (int i = 1; i <= n; ++i) { par[i] = i; rak[i] = 0; } } int find(int u) { if (par[u] != u) par[u] = find(par[u]); return par[u]; } bool join(int u, int v) { u = find(u); v = find(v); if (u == v) return 0; if (rak[u] == rak[v]) ++rak[u]; if (rak[u] < rak[v]) par[u] = v; else par[v] = u; return 1; } namespace sub1 { void solve() { int p[m]; for (int i = 0; i < m; ++i) p[i] = i + 1; vector<int> ans; do { init(n); bool flag = 0; for (int i = 0; i < m; ++i) { if (spec[p[i]]) { if (!join(e[p[i]].fi, e[p[i]].se)) { flag = 1; break; } } else { if (join(e[p[i]].fi, e[p[i]].se)) { flag = 1; break; } } } if (flag) continue; vector<int> res(m); for (int i = 0; i < m; ++i) res[p[i] - 1] = i + 1; if (ans.empty()) ans = res; else ans = min(ans, res); } while (next_permutation(p, p + m)); for (int i: ans) cout << i << ' '; exit(0); } } namespace sub2 { vector<II> adj[N]; int ans[N]; int index; II par[N]; int dep[N]; void build(int u) { for (II ed: adj[u]) { int v = ed.fi, id = ed.se; if (v != par[u].fi) { par[v] = II(u, id); dep[v] = dep[u] + 1; build(v); } } } void getpath(int u, int v, vector<int> &path) { if (dep[u] < dep[v]) swap(u, v); while (dep[u] > dep[v]) { if (ans[par[u].se] == 0) path.push_back(par[u].se); u = par[u].fi; } if (u == v) return; while (u != v) { if (ans[par[u].se] == 0) path.push_back(par[u].se); u = par[u].fi; if (ans[par[v].se] == 0) path.push_back(par[v].se); v = par[v].fi; } } void solve() { for (int i = 1; i < n; ++i) { int u = e[idx[i]].fi, v = e[idx[i]].se; adj[u].push_back(II(v, idx[i])); adj[v].push_back(II(u, idx[i])); } build(1); for (int i = 1; i <= m; ++i) { if (spec[i]) { if (ans[i] == 0) ans[i] = ++index; } else { int u = e[i].fi, v = e[i].se; // đường đi từ u đến v trên cây khung phải được đánh số nhỏ hơn vector<int> path; getpath(u, v, path); sort(path.begin(), path.end()); for (int x: path) { ans[x] = ++index; } ans[i] = ++index; } } for (int i = 1; i <= m; ++i) cout << ans[i] << ' '; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("ZONING.inp", "r")) { freopen("ZONING.inp", "r", stdin); freopen("ZONING.out", "w", stdout); } cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; e[i] = II(u, v); } for (int i = 1; i < n; ++i) { cin >> idx[i]; spec[idx[i]] = 1; } if (m <= 9) sub1::solve(); sub2::solve(); return 0; }

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("ZONING.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen("ZONING.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...