Submission #877190

#TimeUsernameProblemLanguageResultExecution timeMemory
877190fanwenRigged Roads (NOI19_riggedroads)C++17
100 / 100
363 ms50204 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define file(name) \ if(fopen(name".inp", "r")) \ freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \ const int MAX = 3e5 + 5; const int LOG = 18; int N, M, ans[MAX], depth[MAX], numChild[MAX], local[MAX], par[MAX], header[MAX]; vector <int> adj[MAX], mst; vector <pair <int, int>> edges; void dfs(int u, int p) { numChild[u] = 1; par[u] = p; int Max = 0, id = 0; for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) { int v = adj[u][i]; dfs(v, u); numChild[u] += numChild[v]; if(Max < numChild[v]) { Max = numChild[v]; id = i; } } swap(adj[u][id], adj[u][0]); } void HLD(int u) { static int run = 0; local[u] = ++run; for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != par[u]) { int v = adj[u][i]; if(i == 0 && 2 * numChild[v] >= numChild[u]) { depth[v] = depth[u]; header[v] = header[u]; } else { depth[v] = depth[u] + 1; header[v] = v; } HLD(v); } } int itMin[4 * MAX], ind[MAX], pos[MAX]; void build(int idx, int l, int r) { itMin[idx] = -1; if(l == r) { pos[l] = idx; } else { int mid = l + r >> 1; build(idx << 1, l, mid); build(idx << 1 | 1, mid + 1, r); } } void updateMin(int u, int val) { u = pos[u]; itMin[u] = val; while(u > 1) { u >>= 1; itMin[u] = min(itMin[u << 1], itMin[u << 1 | 1]); } } int getMin(int idx, int l, int r, int u, int v) { if(l > v || r < u) return INT_MAX; if(l >= u && r <= v) return itMin[idx]; int mid = l + r >> 1; return min(getMin(idx << 1, l, mid, u, v), getMin(idx << 1 | 1, mid + 1, r, u, v)); } int find_pos_min(int idx, int l, int r, int u, int v) { if(l > v || r < u || itMin[idx] > -1) return -1; if(l == r) return l; int mid = l + r >> 1; int x = find_pos_min(idx << 1, l, mid, u, v); if(x != -1) return x; return find_pos_min(idx << 1 | 1, mid + 1, r, u, v); } void get_path(int l, int r, vector <int> &res) { while(getMin(1, 1, N, l, r) == -1) { int x = find_pos_min(1, 1, N, l, r); res.push_back(ind[x]); updateMin(x, 0); } } vector <int> get_path(int u, int v) { vector <int> ans; if(depth[u] < depth[v]) swap(u, v); while(depth[u] > depth[v]) { get_path(local[header[u]], local[u], ans); u = par[header[u]]; } while(header[u] != header[v]) { get_path(local[header[u]], local[u], ans); get_path(local[header[v]], local[v], ans); u = par[header[u]], v = par[header[v]]; } if(local[u] > local[v]) swap(u, v); get_path(local[u] + 1, local[v], ans); return ans; } void you_make_it(void) { cin >> N >> M; edges.resize(M + 1); for (int i = 1; i <= M; ++i) { cin >> edges[i].fi >> edges[i].se; } for (int i = 1; i < N; ++i) { int x; cin >> x; auto [u, v] = edges[x]; adj[u].push_back(v); adj[v].push_back(u); mst.push_back(x); } fill(ans + 1, ans + M + 1, -1); dfs(1, 0); depth[1] = header[1] = 1; HLD(1); for (int x : mst) { auto &[u, v] = edges[x]; if(v == par[u]) swap(u, v); ind[local[v]] = x; } build(1, 1, N); int cur = 1; for (int i = 1; i <= M; ++i) { if(ans[i] != -1) continue; auto [u, v] = edges[i]; vector <int> res = get_path(u, v); sort(res.begin(), res.end()); for (auto x : res) { ans[x] = cur++; } if(ans[i] == -1) { ans[i] = cur++; } } for (int i = 1; i <= M; ++i) cout << ans[i] << " \n"[i == M]; } signed main() { #ifdef LOCAL freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif file("riggedroads"); auto start_time = chrono::steady_clock::now(); cin.tie(0), cout.tie(0) -> sync_with_stdio(0); you_make_it(); auto end_time = chrono::steady_clock::now(); cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); } // Dream it. Wish it. Do it.

Compilation message (stderr)

riggedroads.cpp: In function 'void build(int, int, int)':
riggedroads.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid = l + r >> 1;
      |             ~~^~~
riggedroads.cpp: In function 'int getMin(int, int, int, int, int)':
riggedroads.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |  int mid = l + r >> 1;
      |            ~~^~~
riggedroads.cpp: In function 'int find_pos_min(int, int, int, int, int)':
riggedroads.cpp:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid = l + r >> 1;
      |            ~~^~~
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:171:5: note: in expansion of macro 'file'
  171 |     file("riggedroads");
      |     ^~~~
riggedroads.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:171:5: note: in expansion of macro 'file'
  171 |     file("riggedroads");
      |     ^~~~
#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...