oj.uz

답안 #871768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871768 2023-11-11T14:12:15 Z sunwukong123 동기화 (JOI13_synchronization) C++14
0 / 100
 107 ms 34028 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 100005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
/*
you need a "dynamic UFDS" on tree which supports connection and deletion between parent and child nodes
when disconnecting, carry the ans from the current ufds group's root to this ufds group's root. 
when connecting, add the ans for the child's ufds group to the parent's ufds group. (keep track of how many more nodes there are now)
*/
int twok[MAXN][18];
int st[MAXN], en[MAXN];
int TIME=1;
vector<int> adj[MAXN];
int n,m,q;
int ans[MAXN], lst[MAXN], state[MAXN];
namespace fw {
	int fw[MAXN];
	void update(int x, int nval){
		for(;x<MAXN;x+=x&-x)fw[x]+=nval;
	}
	void update(int x,int y, int nval){
		update(x,nval);
		update(y+1,-nval);
	}
	int query(int x){
		int res=0;
		for(;x;x-=x&-x)res+=fw[x];
		return res;
	}
};
int find(int x){ // finds the parent
	for(int i=17;i>=0;i--){
		if(twok[x][i]==-1)continue;
		if(fw::query(st[x]) == fw::query(st[twok[x][i]])){
			x=twok[x][i];
		}
	}
	return x;
}
void dfs(int x, int p){
	st[x]=TIME++;
	twok[x][0]=p;
	for(auto v:adj[x])if(v!=p){
		dfs(v,x);
	}
	for(int i=1;i<=17;i++){
		if(twok[x][i-1] == -1)continue;

		twok[x][i]=twok[twok[x][i-1]][i-1];
	}

	en[x]=TIME-1;
}
pi E[MAXN];
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	memset(twok,-1,sizeof twok);
	cin >> n >> m >> q;
	for(int i=1;i<=n-1;i++){
		int a,b; cin >> a >> b;
		E[i].first=a;
		E[i].second=b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++)ans[i]=1;

	dfs(1,-1);
	for(int i=1;i<=n;i++){
		fw::update(st[i],en[i],1);//there is blockage between child and parent.
	}

	for(int t=1;t<=m;t++){

		int edge; cin >> edge;
		int par=E[edge].first;
		int child=E[edge].second;
		if(st[par]>st[child])swap(par,child); // st[par]<st[child]

		if(!state[edge]){ // activate
			int rt=find(par);
			ans[rt] += ans[child] - lst[child];
			fw::update(st[child],en[child],-1);
		} else{
			int rt=find(par);
			ans[child]=lst[child]=ans[rt];
			fw::update(st[child],en[child],1);
		}
		state[edge] = !state[edge];
	}
	while(q--){
		int x; cin >> x;
		cout<<ans[find(x)]<<"\n";
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22876 KB Output is correct
4 Correct 4 ms 22876 KB Output is correct
5 Incorrect 3 ms 22876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 30984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 23028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 34028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Incorrect 4 ms 22876 KB Output isn't correct
5 Halted 0 ms 0 KB -