Submission #1278334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278334		wedonttalkanymore	동기화 (JOI13_synchronization)	C++20	100 / 100	230 ms	39748 KiB

synchronization

#include <bits/stdc++.h>
/*
    10 mins AC -> 40 mins subtasks + code
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 3e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, m, q;
int U[N], V[N];
vector <int> adj[N];
int New[N], Old[N];
bool on[N];

struct ST {
    vector <int> st;
    ST (int _n) {
        st.assign(4 * (_n + 1), 0);
    }
    void build(int i, int l, int r) {
    	if (l == r) {
    		st[i] = l;
    		return;
		}
		int mid = (l + r) / 2;
		build(2 * i, l, mid);
		build(2 * i + 1, mid + 1, r);
		st[i] = max(st[2 * i], st[2 * i + 1]);
	}
    void update(int i, int l, int r, int pos, int val) {
        if (l == r) {
            st[i] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2 * i, l, mid, pos, val);
        else update(2 * i + 1, mid + 1, r, pos, val);
        st[i] = max(st[2 * i], st[2 * i + 1]);
    }
    int get(int i, int l, int r, int u, int v) {
        if (u > r || v < l) return -inf;
        if (u <= l && r <= v) return st[i];
        int mid = (l + r) / 2;
        return max(get(2 * i, l, mid, u, v), get(2 * i + 1, mid + 1, r, u, v));
    }
} st(N);

struct HLD {
    int par[N], sz[N], depth[N], heavy[N];
    void dfs(int u, int parent) {
        par[u] = parent;
        sz[u] = 1;
        for (auto v : adj[u]) {
            if (v != parent) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
                if (sz[heavy[u]] < sz[v]) heavy[u] = v;
                sz[u] += sz[v];
            }
        }
    }
    int in[N], timedfs = 0, head[N];
    int euler[N];
    void decompose(int u, int chain) {
        in[u] = ++timedfs;
        euler[timedfs] = u;
        head[u] = chain;
        if (heavy[u]) decompose(heavy[u], chain);
        for (auto v : adj[u]) {
            if (v != heavy[u] && v != par[u]) decompose(v, v);
        }
    }
    int get(int u, int v) {
//    	cout << u << ' ' << v << '\n';
        int res = -inf;
        while(head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            int val = st.get(1, 1, n, in[head[v]], in[v]);
            res = max(res, val);
            v = par[head[v]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        res = max(res, st.get(1, 1, n, in[u], in[v]));
        return euler[res];
    }
} hld;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> U[i] >> V[i];
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    hld.dfs(1, 1);
    hld.decompose(1, 1);
    st.build(1, 1, n);
//    for (int i = 1; i <= n; i++) cout << hld.heavy[i] << ' ';
    for (int i = 1; i <= n; i++) New[i] = 1;
    for (int i = 1; i <= m; i++) {
        int idx;
        cin >> idx;
        int u = U[idx], v = V[idx];
        if (hld.par[u] == v) swap(u, v); // u la cha v
        if (on[idx]) {
            int anc = hld.get(u, 1);
            New[v] = New[anc];
            Old[v] = New[anc];
            st.update(1, 1, n, hld.in[v], hld.in[v]);
        }
        else {
            int anc = hld.get(u, 1);
            New[anc] += New[v] - Old[v];
            st.update(1, 1, n, hld.in[v], -inf);
        }
        on[idx] = 1 - on[idx];
    }
    for (int i = 1; i <= q; i++) {
    	int x;
    	cin >> x;
        int anc = hld.get(x, 1);
        cout << New[anc] << '\n';
    }
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
synchronization.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40