oj.uz

Submission #123363

# Submission time Handle Problem Language Result Execution time Memory
123363 2019-07-01T08:26:23 Z baluteshih Tropical Garden (IOI11_garden) C++14
100 / 100
 4439 ms 31612 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> Gr[150005],cir[300005],nG[300005],ans[2];
int to[300005],in[300005],bln[300005],pl[300005],preans[300005];

void dfs1(int u,int d)
{
	if(u&1^1) ++preans[d];
	for(int i:nG[u])
		dfs1(i,d+1);
}

void dfs2(int u,int d,int t)
{
	if(u&1^1) ans[t].pb(d);
	for(int i:nG[u])
		dfs2(i,d+1,t);
}

void doit(int x,int t)
{
	if(!bln[x])
		dfs1(x,0);
	else
	{
		for(int i=0;i<cir[bln[x]].size();++i)
			dfs2(cir[bln[x]][(pl[x]-i+cir[bln[x]].size())%cir[bln[x]].size()],i,t);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int tp=0;
	queue<int> q;
	for(int i=0;i<M;++i)
		Gr[R[i][0]].pb(R[i][1]),Gr[R[i][1]].pb(R[i][0]);
	for(int i=0;i<N;++i)
	{
		if(i==Gr[Gr[i][0]][0])
			to[i<<1]=Gr[i][0]<<1|1;
		else
			to[i<<1]=Gr[i][0]<<1;
		if(Gr[i].size()>1)
			if(i==Gr[Gr[i][1]][0])
				to[i<<1|1]=Gr[i][1]<<1|1;
			else
				to[i<<1|1]=Gr[i][1]<<1;
		else
			if(i==Gr[Gr[i][0]][0])
				to[i<<1|1]=Gr[i][0]<<1|1;
			else
				to[i<<1|1]=Gr[i][0]<<1;
		++in[to[i<<1]],++in[to[i<<1|1]];
	}
	for(int i=0;i<2*N;++i)
		if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(--in[to[u]]==0) q.push(to[u]);
		nG[to[u]].pb(u);
	}
	for(int i=0;i<2*N;++i)
		if(in[i])
		{
			++tp;
			for(int j=i;in[j];j=to[j])
				in[j]=0,bln[j]=tp,pl[j]=cir[tp].size(),cir[tp].pb(j);
		}
	doit(P<<1,0),doit(P<<1|1,1);
	sort(ALL(ans[0])),sort(ALL(ans[1]));
	for(int i=0;i<Q;++i)
	{
		int rt=0;
		if(G[i]<2*N) rt+=preans[G[i]];
		for(int t=0;t<2;++t)
			if(bln[P<<1|t])
				for(auto j:ans[t])
					if(j>G[i]) break;
					else 
						rt+=((G[i]-j)%cir[bln[P<<1|t]].size()==0);
		answer(rt);
	}
}

Compilation message

garden.cpp: In function 'void dfs1(int, int)':
garden.cpp:23:6: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if(u&1^1) ++preans[d];
     ~^~
garden.cpp: In function 'void dfs2(int, int, int)':
garden.cpp:30:6: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if(u&1^1) ans[t].pb(d);
     ~^~
garden.cpp: In function 'void doit(int, int)':
garden.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cir[bln[x]].size();++i)
               ~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:93:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
    if(bln[P<<1|t])
      ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18104 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 19 ms 18052 KB Output is correct
4 Correct 18 ms 17916 KB Output is correct
5 Correct 19 ms 18000 KB Output is correct
6 Correct 19 ms 18140 KB Output is correct
7 Correct 19 ms 18040 KB Output is correct
8 Correct 19 ms 18040 KB Output is correct
9 Correct 21 ms 18172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18104 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 19 ms 18052 KB Output is correct
4 Correct 18 ms 17916 KB Output is correct
5 Correct 19 ms 18000 KB Output is correct
6 Correct 19 ms 18140 KB Output is correct
7 Correct 19 ms 18040 KB Output is correct
8 Correct 19 ms 18040 KB Output is correct
9 Correct 21 ms 18172 KB Output is correct
10 Correct 18 ms 18040 KB Output is correct
11 Correct 31 ms 19836 KB Output is correct
12 Correct 53 ms 21624 KB Output is correct
13 Correct 64 ms 25960 KB Output is correct
14 Correct 178 ms 30344 KB Output is correct
15 Correct 202 ms 31612 KB Output is correct
16 Correct 155 ms 27592 KB Output is correct
17 Correct 136 ms 26704 KB Output is correct
18 Correct 56 ms 22040 KB Output is correct
19 Correct 181 ms 30392 KB Output is correct
20 Correct 207 ms 31124 KB Output is correct
21 Correct 156 ms 27988 KB Output is correct
22 Correct 139 ms 26540 KB Output is correct
23 Correct 182 ms 31296 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18104 KB Output is correct
2 Correct 18 ms 18168 KB Output is correct
3 Correct 19 ms 18052 KB Output is correct
4 Correct 18 ms 17916 KB Output is correct
5 Correct 19 ms 18000 KB Output is correct
6 Correct 19 ms 18140 KB Output is correct
7 Correct 19 ms 18040 KB Output is correct
8 Correct 19 ms 18040 KB Output is correct
9 Correct 21 ms 18172 KB Output is correct
10 Correct 18 ms 18040 KB Output is correct
11 Correct 31 ms 19836 KB Output is correct
12 Correct 53 ms 21624 KB Output is correct
13 Correct 64 ms 25960 KB Output is correct
14 Correct 178 ms 30344 KB Output is correct
15 Correct 202 ms 31612 KB Output is correct
16 Correct 155 ms 27592 KB Output is correct
17 Correct 136 ms 26704 KB Output is correct
18 Correct 56 ms 22040 KB Output is correct
19 Correct 181 ms 30392 KB Output is correct
20 Correct 207 ms 31124 KB Output is correct
21 Correct 156 ms 27988 KB Output is correct
22 Correct 139 ms 26540 KB Output is correct
23 Correct 182 ms 31296 KB Output is correct
24 Correct 20 ms 18048 KB Output is correct
25 Correct 90 ms 19944 KB Output is correct
26 Correct 78 ms 21632 KB Output is correct
27 Correct 4439 ms 25904 KB Output is correct
28 Correct 775 ms 30488 KB Output is correct
29 Correct 3641 ms 31160 KB Output is correct
30 Correct 2466 ms 27600 KB Output is correct
31 Correct 2039 ms 26672 KB Output is correct
32 Correct 56 ms 21724 KB Output is correct
33 Correct 787 ms 30464 KB Output is correct
34 Correct 3584 ms 31600 KB Output is correct
35 Correct 2496 ms 27900 KB Output is correct
36 Correct 2039 ms 26712 KB Output is correct
37 Correct 537 ms 31484 KB Output is correct
38 Correct 4003 ms 30892 KB Output is correct