oj.uz

Submission #94004

# Submission time Handle Problem Language Result Execution time Memory
94004 2019-01-14T14:18:40 Z fjzzq2002 Tropical Garden (IOI11_garden) C++14
100 / 100
 423 ms 106696 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace Wrap
{
#define SZ 666666
int n,m,N,p,a[SZ],b[SZ],u[SZ];
int gb(int e,int t)
{return a[e]^b[e]^t;}
vector<int> e[SZ],pre[SZ];
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
struct Sup
{
vector<int> v[SZ];
int GA;
map<int,vector<int> > sb;
void init(int x)
{
	queue<pii> q;
	q.push(pii(x,0));
	while(!q.empty())
	{
		pii w=q.front(); q.pop();
		if(v[w.fi].size()>1) continue;
		v[w.fi].pb(w.se);
		for(auto g:pre[w.fi])
			q.push(pii(g,w.se+1));
	}
	GA=-1;
	for(int i=0;i<N;++i) if(v[i].size()&&i%2==0)
	{
		int G=(v[i].size()>=2)?(v[i][1]-v[i][0]):(1.01e9);
		if(GA==-1) GA=G;
		sb[v[i][0]%G].pb(v[i][0]/G);
	}
	for(auto&u:sb)
		sort(u.se.begin(),u.se.end());
}
int qry(int x)
{
	if(GA==-1) return 0;
	auto&w=sb[x%GA];
	return upper_bound(w.begin(),w.end(),x/GA)-w.begin();
}
}A,B;
}
void count_routes(int N_, int M, int P, int R[][2], int Q, int G[])
{
	using namespace Wrap;
	n=N_,m=M,p=P,N=n*2;
	for(int i=0;i<m;++i)
		a[i]=R[i][0],b[i]=R[i][1],
		e[a[i]].pb(i),e[b[i]].pb(i);
	for(int i=0;i<n;++i)
		for(int j=0;j<2;++j)
		{
			int c=e[i].front();
			if(j&&e[i].size()>1)
				c=e[i][1];
			int w=gb(c,i);
			int d=(e[w].front()==c);
			u[i*2+j]=w*2+d;
			pre[w*2+d].pb(i*2+j);
		}
	A.init(P*2);
	B.init(P*2+1);
	for(int j=0;j<Q;++j)
		answer(A.qry(G[j])+B.qry(G[j]));
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 63184 KB Output is correct
2 Correct 70 ms 63208 KB Output is correct
3 Correct 62 ms 63136 KB Output is correct
4 Correct 61 ms 62956 KB Output is correct
5 Correct 61 ms 62972 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 72 ms 63068 KB Output is correct
8 Correct 59 ms 63172 KB Output is correct
9 Correct 64 ms 63388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 63184 KB Output is correct
2 Correct 70 ms 63208 KB Output is correct
3 Correct 62 ms 63136 KB Output is correct
4 Correct 61 ms 62956 KB Output is correct
5 Correct 61 ms 62972 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 72 ms 63068 KB Output is correct
8 Correct 59 ms 63172 KB Output is correct
9 Correct 64 ms 63388 KB Output is correct
10 Correct 62 ms 63016 KB Output is correct
11 Correct 75 ms 65500 KB Output is correct
12 Correct 108 ms 66868 KB Output is correct
13 Correct 263 ms 102488 KB Output is correct
14 Correct 290 ms 77024 KB Output is correct
15 Correct 422 ms 84916 KB Output is correct
16 Correct 332 ms 78888 KB Output is correct
17 Correct 276 ms 77136 KB Output is correct
18 Correct 106 ms 66812 KB Output is correct
19 Correct 263 ms 76656 KB Output is correct
20 Correct 420 ms 84776 KB Output is correct
21 Correct 328 ms 78620 KB Output is correct
22 Correct 290 ms 76776 KB Output is correct
23 Correct 318 ms 77468 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 63184 KB Output is correct
2 Correct 70 ms 63208 KB Output is correct
3 Correct 62 ms 63136 KB Output is correct
4 Correct 61 ms 62956 KB Output is correct
5 Correct 61 ms 62972 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 72 ms 63068 KB Output is correct
8 Correct 59 ms 63172 KB Output is correct
9 Correct 64 ms 63388 KB Output is correct
10 Correct 62 ms 63016 KB Output is correct
11 Correct 75 ms 65500 KB Output is correct
12 Correct 108 ms 66868 KB Output is correct
13 Correct 263 ms 102488 KB Output is correct
14 Correct 290 ms 77024 KB Output is correct
15 Correct 422 ms 84916 KB Output is correct
16 Correct 332 ms 78888 KB Output is correct
17 Correct 276 ms 77136 KB Output is correct
18 Correct 106 ms 66812 KB Output is correct
19 Correct 263 ms 76656 KB Output is correct
20 Correct 420 ms 84776 KB Output is correct
21 Correct 328 ms 78620 KB Output is correct
22 Correct 290 ms 76776 KB Output is correct
23 Correct 318 ms 77468 KB Output is correct
24 Correct 62 ms 63068 KB Output is correct
25 Correct 77 ms 65656 KB Output is correct
26 Correct 103 ms 66944 KB Output is correct
27 Correct 228 ms 102608 KB Output is correct
28 Correct 272 ms 77040 KB Output is correct
29 Correct 416 ms 84952 KB Output is correct
30 Correct 323 ms 79004 KB Output is correct
31 Correct 286 ms 77048 KB Output is correct
32 Correct 107 ms 67108 KB Output is correct
33 Correct 260 ms 76984 KB Output is correct
34 Correct 423 ms 84892 KB Output is correct
35 Correct 322 ms 78800 KB Output is correct
36 Correct 317 ms 78744 KB Output is correct
37 Correct 259 ms 77552 KB Output is correct
38 Correct 337 ms 106696 KB Output is correct