oj.uz

Submission #94957

# Submission time Handle Problem Language Result Execution time Memory
94957 2019-01-25T16:44:20 Z MvC Synchronization (JOI13_synchronization) C++11
100 / 100
 442 ms 23660 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);
                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 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 5240 KB Output is correct
7 Correct 17 ms 6648 KB Output is correct
8 Correct 17 ms 6648 KB Output is correct
9 Correct 17 ms 6648 KB Output is correct
10 Correct 227 ms 19916 KB Output is correct
11 Correct 225 ms 19816 KB Output is correct
12 Correct 236 ms 23004 KB Output is correct
13 Correct 93 ms 20204 KB Output is correct
14 Correct 134 ms 19800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20712 KB Output is correct
2 Correct 85 ms 20460 KB Output is correct
3 Correct 88 ms 22296 KB Output is correct
4 Correct 93 ms 22164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 7 ms 5084 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 33 ms 6904 KB Output is correct
8 Correct 374 ms 22540 KB Output is correct
9 Correct 355 ms 22384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 22432 KB Output is correct
2 Correct 287 ms 22832 KB Output is correct
3 Correct 263 ms 22992 KB Output is correct
4 Correct 265 ms 22884 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 34 ms 6812 KB Output is correct
7 Correct 387 ms 20188 KB Output is correct
8 Correct 385 ms 23332 KB Output is correct
9 Correct 251 ms 20628 KB Output is correct
10 Correct 306 ms 20460 KB Output is correct
11 Correct 237 ms 22200 KB Output is correct
12 Correct 238 ms 22124 KB Output is correct
13 Correct 272 ms 23660 KB Output is correct