제출 #1292987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292987		shidou26	동기화 (JOI13_synchronization)	C++20	100 / 100	203 ms	24092 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 5e5 + 3;

int n, m, q;
pii edge[N];
vector<int> adj[N];

void input() {
	cin >> n >> m >> q;

	for(int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		edge[i] = {u, v};
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

const int LOG = 21;

int timer;
int dep[N], tin[N], tout[N], par[N][LOG];
int answer[N], last[N];
bool state[N];

struct FenwickTree {
	vector<int> tr;
	FenwickTree (int n = 0) : tr(n + 3) {}

	void update(int p, int v) {
		for(; p < sz(tr); p += p & -p) tr[p] += v;
	}

	void update(int l, int r, int v) {
		update(l, v);
		update(r + 1, -v);
	}

	int get(int p) {
		int tot = 0;
		for(; p > 0; p -= p & -p) tot += tr[p];
		return tot;
	}
} active;

void dfs(int u, int p) {
	tin[u] = ++timer;
	for(int v : adj[u]) if(v != p) {
		dep[v] = dep[u] + 1;
		par[v][0] = u;
		for(int j = 1; j < LOG; j++) par[v][j] = par[par[v][j - 1]][j - 1];
		dfs(v, u);
	}
	tout[u] = timer;
}

int root(int u) {
	for(int i = LOG - 1; i >= 0; i--) {
		if(par[u][i] && dep[par[u][i]] - active.get(tin[par[u][i]]) == dep[u] - active.get(tin[u])) {
			u = par[u][i];
		}  
	}

	return u;
}

void process() {
	dfs(1, -1);

	for(int i = 1; i < n; i++) {
		auto &[u, v] = edge[i];
		if(dep[u] > dep[v]) swap(u, v);
	}

	active = FenwickTree(n);
	fill(answer + 1, answer + 1 + n, 1);

	for(int i = 1; i <= m; i++) {
		int d; cin >> d;
		auto [p, u] = edge[d];

		if(!state[d]) {
			answer[root(p)] += answer[u] - last[u];
			active.update(tin[u], tout[u], 1);
			state[d] = true;
		}else {
			answer[u] = last[u] = answer[root(p)];
			active.update(tin[u], tout[u], -1);
			state[d] = false;
		}

		// cout << dbg(p) << dbg(u) << endl;
		// for(int j = 1; j <= n; j++) cout << root(tin[j]) << " \n"[j == n];
	}

	while(q--) {
		int u; cin >> u;
		cout << answer[root(u)] << endl; 
	}
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int testcase = 1; // cin >> testcase;    
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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