답안 #94958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94958 2019-01-25T16:45:14 Z MvC 동기화 (JOI13_synchronization) C++11
100 / 100
527 ms 22956 KB
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int x,y,i,n,up[nmax][20],tin[nmax],tout[nmax],t,v,ans[nmax],q,m,fw[nmax],lst[nmax];
vector<int>a[nmax];
vector<pair<int,int> >e;
void dfs(int x,int p)
{
    tin[x]=++t;
    up[x][0]=p;
    for(int i=1;i<20;i++)up[x][i]=up[up[x][i-1]][i-1];
    for(int i=0;i<a[x].size();i++)if(a[x][i]!=p)dfs(a[x][i],x);
    tout[x]=t+1;
}
void upd(int i,int v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
int qry(int i)
{
	int rs=0;
	for(;i>=1;i-=i&(-i))rs+=fw[i];
	return rs;
}
int get(int x)
{
	int y=qry(tin[x]);
	for(int i=19;i>=0;i--)if(qry(tin[up[x][i]])==y)x=up[x][i];
	return x;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(i=1;i<n;i++)
    {
        cin>>x>>y;
        e.pb({x,y});
        a[x].pb(y);
        a[y].pb(x);
    }
    dfs(1,1);
    for(i=0;i<n-1;i++)if(tin[e[i].fr]>tin[e[i].sc])swap(e[i].fr,e[i].sc);
	for(i=1;i<=n;i++)
	{
		upd(tin[i],1);
		upd(tout[i],-1);
		ans[i]=1;
	}
	while(m--)
	{
		cin>>i;
		x=e[i-1].fr,y=e[i-1].sc,v=get(x);
		if(lst[i]==-1)
		{
			upd(tin[y],1);
			upd(tout[y],-1);
			ans[y]=lst[i]=ans[v];
		}
		else
		{
			upd(tin[y],-1);
			upd(tout[y],1);
			ans[v]+=ans[y]-lst[i];
			lst[i]=-1;
		}
	}
	while(q--)
	{
		cin>>x;
		cout<<ans[get(x)]<<endl;
	}
    return 0;
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a[x].size();i++)if(a[x][i]!=p)dfs(a[x][i],x);
                 ~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 25 ms 6392 KB Output is correct
8 Correct 26 ms 6520 KB Output is correct
9 Correct 22 ms 6520 KB Output is correct
10 Correct 325 ms 18920 KB Output is correct
11 Correct 308 ms 18896 KB Output is correct
12 Correct 288 ms 22248 KB Output is correct
13 Correct 181 ms 19180 KB Output is correct
14 Correct 217 ms 18924 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 20716 KB Output is correct
2 Correct 158 ms 20644 KB Output is correct
3 Correct 150 ms 22164 KB Output is correct
4 Correct 150 ms 22124 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4988 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5116 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 43 ms 6904 KB Output is correct
8 Correct 488 ms 22512 KB Output is correct
9 Correct 506 ms 22368 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 22364 KB Output is correct
2 Correct 355 ms 22760 KB Output is correct
3 Correct 358 ms 22900 KB Output is correct
4 Correct 351 ms 22772 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 42 ms 6532 KB Output is correct
7 Correct 527 ms 19280 KB Output is correct
8 Correct 511 ms 22504 KB Output is correct
9 Correct 372 ms 19708 KB Output is correct
10 Correct 444 ms 19564 KB Output is correct
11 Correct 358 ms 21492 KB Output is correct
12 Correct 345 ms 21260 KB Output is correct
13 Correct 379 ms 22956 KB Output is correct