oj.uz

Submission #636591

# Submission time Handle Problem Language Result Execution time Memory
636591 2022-08-29T16:16:56 Z Karliver Synchronization (JOI13_synchronization) C++17
100 / 100
 225 ms 36428 KB 
	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int MOD = 998244353;
const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}



void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)


int nd[N], par[N], S[N], tin[N], w[N], ans[N], com[N], head[N];
int T = 0;

vector<pair<int, int>> g[N];

void dfs(int v) {
	S[v] = 1;
	for(auto &E : g[v]) {
		auto [y, i] = E;
		nd[i] = y;
		par[y] = v;
		g[y].erase(find(all(g[y]), make_pair(v, i)));
		dfs(y);
		S[v] += S[y];
		if(S[y] > S[g[v][0].first]) swap(g[v][0], E);
	}
}


void dfs_hld(int v) {
	w[T] = v;
	tin[v] = T++;
		
	for(auto [y, i] : g[v]) {
		head[y] = (y == g[v][0].first ? head[v] : y);
		dfs_hld(y);
	}
}

set<int> roots[N];

int grt(int y) {
	
	while(roots[head[y]].empty() || *roots[head[y]].begin() > tin[y]) {
		y = par[head[y]];
	}
	return w[*--roots[head[y]].upper_bound(tin[y])];
}

bool active[N];

void solve() {
	
	int n, m, q;
	cin >> n >> m >> q;
	
	forn(i, n - 1) {
		int a, b;
		cin >> a >> b;
		--a;--b;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	dfs(0);
	dfs_hld(0);
	
	
	forn(i, n) {
		ans[i] = 1;
		roots[head[i]].insert(tin[i]);
		
	}
	
	while(m--) {
		int j;
		cin >> j;
		--j;
		if(!active[j]) {
			int y = nd[j];
			int rt = grt(par[y]);
			ans[rt] += ans[y]-com[y];
			//debug(y, rt);
			roots[head[y]].erase(tin[y]);
		}
		else {
			int y = nd[j];
			int rt = grt(y);
			ans[y] = com[y] = ans[rt];
			roots[head[y]].insert(tin[y]);
		}
		
		active[j] = !active[j];
	}
	
	while(q--) {
		int x;
		cin >> x;
		--x;
		cout << ans[grt(x)] << '\n';
	}
	
		
	
}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14372 KB Output is correct
3 Correct 7 ms 14516 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14436 KB Output is correct
6 Correct 8 ms 14572 KB Output is correct
7 Correct 17 ms 15700 KB Output is correct
8 Correct 17 ms 15700 KB Output is correct
9 Correct 18 ms 15796 KB Output is correct
10 Correct 163 ms 28364 KB Output is correct
11 Correct 161 ms 28396 KB Output is correct
12 Correct 225 ms 35608 KB Output is correct
13 Correct 91 ms 28196 KB Output is correct
14 Correct 114 ms 27452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 31480 KB Output is correct
2 Correct 66 ms 31212 KB Output is correct
3 Correct 78 ms 34672 KB Output is correct
4 Correct 80 ms 34636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14432 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 7 ms 14408 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 22 ms 16576 KB Output is correct
8 Correct 210 ms 36420 KB Output is correct
9 Correct 220 ms 36300 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 36376 KB Output is correct
2 Correct 93 ms 35716 KB Output is correct
3 Correct 96 ms 35820 KB Output is correct
4 Correct 95 ms 35892 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 18 ms 15828 KB Output is correct
7 Correct 190 ms 29288 KB Output is correct
8 Correct 203 ms 36428 KB Output is correct
9 Correct 108 ms 29348 KB Output is correct
10 Correct 147 ms 28604 KB Output is correct
11 Correct 89 ms 32652 KB Output is correct
12 Correct 85 ms 32712 KB Output is correct
13 Correct 95 ms 35820 KB Output is correct