Submission #1258603

#TimeUsernameProblemLanguageResultExecution timeMemory
1258603CrabCNH동기화 (JOI13_synchronization)C++20
100 / 100
325 ms35108 KiB
#include <bits/stdc++.h> #define task "BriantheCrab" #define int long long #define pii pair <int, int> #define fi first #define se second #define szf sizeof #define sz(s) (int)((s).size()) #define all(v) (v).begin(), (v).end() typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; template <class T> void minimize (T &t, T f) {if (t > f) t = f;} template <class T> void maximize (T &t, T f) {if (t < f) t = f;} const int maxN = 2e5 + 5; const int inf = 1e18 + 7; const int mod = 1e9 + 7; const int LOG = 20; // khong tu code thi khong kha len duoc dau // biet sol roi thi tu lam not di struct Fenwick { vector <int> bit; int n; inline void init () { bit.resize (n + 2, 0); } inline void upd (int id, int val) { for (; id < n; id += id & (-id)) { bit[id] += val; } } inline int get (int id) { int res = 0; for (; id; id -= id & (-id)) { res += bit[id]; } return res; } }; int n, m, q; int res[maxN], lst[maxN], up[maxN][LOG], h[maxN]; int tIn[maxN], tOut[maxN]; int timer = 0; vector <pii> ed; vector <int> adj[maxN]; bool merged[maxN]; Fenwick T; void dfs (int u, int p) { up[u][0] = p; tIn[u] = ++timer; for (int j = 1; j < LOG; j ++) { up[u][j] = up[up[u][j - 1]][j - 1]; } for (auto v : adj[u]) { if (v == p) { continue; } h[v] = h[u] + 1; dfs (v, u); } tOut[u] = timer; } inline int jump (int u) { for (int j = LOG - 1; j >= 0; j --) { if (T.get (tIn[up[u][j]]) == T.get (tIn[u])) { u = up[u][j]; } } return u; } inline void print () { cout << "print\n"; for (int i = 1; i <= n; i ++) { cout << T.get (tIn[i]) << ' '; } cout << '\n'; } void solve () { cin >> n >> m >> q; for (int i = 1; i <= n - 1; i ++) { int u, v; cin >> u >> v; adj[u].push_back (v); adj[v].push_back (u); ed.push_back ({u, v}); } dfs (1, 1); T.n = timer + 2; T.init (); for (int i = 1; i <= n; i ++) { res[i] = 1; T.upd (tIn[i], 1); T.upd (tOut[i] + 1, -1); } //print (); for (int i = 1; i <= m; i ++) { int x; cin >> x; auto [u, v] = ed[x - 1]; if (h[u] > h[v]) { swap (u, v); } if (merged[x] == 0) { //cout << u << ' ' << v << ' ' << jump (u) << '\n'; res[jump (u)] += res[v] - lst[v]; T.upd (tIn[v], -1); T.upd (tOut[v] + 1, 1); //cout << tIn[i] << ' ' << tOut[i] << '\n'; merged[x] = 1; } else { res[v] = lst[v] = res[jump (u)]; T.upd (tIn[v], 1); T.upd (tOut[v] + 1, -1); //cout << tIn[i] << ' ' << tOut[i] << '\n'; merged[x] = 0; } //print (); } while (q --) { int x; cin >> x; cout << res[jump (x)] << '\n'; } return; } signed main () { cin.tie (nullptr) -> sync_with_stdio (false); if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } int t = 1; //cin >> t; while (t --) { solve (); } return 0; } // thfv

Compilation message (stderr)

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