oj.uz

Submission #94002

# Submission time Handle Problem Language Result Execution time Memory
94002 2019-01-14T14:13:22 Z fjzzq2002 Tropical Garden (IOI11_garden) C++14
100 / 100
 622 ms 106820 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(w.se>100) continue;
		if(v[w.fi].size()>3) 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((v[i].size()==3&&v[i][2]-v[i][1]!=G)||v[i].size()==2)
			throw "GG";
		if(GA==-1) GA=G;
		if(GA!=G) throw "GG";
		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)
{
//	int ans=0;
//	for(int i=0;i<N;i+=2)
//		ans+=binary_search(v[i].begin(),v[i].end(),x);
//	return ans;
	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 61 ms 63140 KB Output is correct
2 Correct 61 ms 63192 KB Output is correct
3 Correct 61 ms 63232 KB Output is correct
4 Correct 61 ms 62972 KB Output is correct
5 Correct 60 ms 62976 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 59 ms 63068 KB Output is correct
8 Correct 62 ms 63096 KB Output is correct
9 Correct 64 ms 63324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 63140 KB Output is correct
2 Correct 61 ms 63192 KB Output is correct
3 Correct 61 ms 63232 KB Output is correct
4 Correct 61 ms 62972 KB Output is correct
5 Correct 60 ms 62976 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 59 ms 63068 KB Output is correct
8 Correct 62 ms 63096 KB Output is correct
9 Correct 64 ms 63324 KB Output is correct
10 Correct 66 ms 63000 KB Output is correct
11 Correct 94 ms 65728 KB Output is correct
12 Correct 101 ms 67212 KB Output is correct
13 Correct 261 ms 102792 KB Output is correct
14 Correct 271 ms 77412 KB Output is correct
15 Correct 500 ms 85376 KB Output is correct
16 Correct 389 ms 79236 KB Output is correct
17 Correct 333 ms 77416 KB Output is correct
18 Correct 100 ms 66908 KB Output is correct
19 Correct 275 ms 77168 KB Output is correct
20 Correct 516 ms 85300 KB Output is correct
21 Correct 391 ms 78972 KB Output is correct
22 Correct 339 ms 77140 KB Output is correct
23 Correct 273 ms 77824 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 63140 KB Output is correct
2 Correct 61 ms 63192 KB Output is correct
3 Correct 61 ms 63232 KB Output is correct
4 Correct 61 ms 62972 KB Output is correct
5 Correct 60 ms 62976 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct
7 Correct 59 ms 63068 KB Output is correct
8 Correct 62 ms 63096 KB Output is correct
9 Correct 64 ms 63324 KB Output is correct
10 Correct 66 ms 63000 KB Output is correct
11 Correct 94 ms 65728 KB Output is correct
12 Correct 101 ms 67212 KB Output is correct
13 Correct 261 ms 102792 KB Output is correct
14 Correct 271 ms 77412 KB Output is correct
15 Correct 500 ms 85376 KB Output is correct
16 Correct 389 ms 79236 KB Output is correct
17 Correct 333 ms 77416 KB Output is correct
18 Correct 100 ms 66908 KB Output is correct
19 Correct 275 ms 77168 KB Output is correct
20 Correct 516 ms 85300 KB Output is correct
21 Correct 391 ms 78972 KB Output is correct
22 Correct 339 ms 77140 KB Output is correct
23 Correct 273 ms 77824 KB Output is correct
24 Correct 62 ms 63020 KB Output is correct
25 Correct 76 ms 65528 KB Output is correct
26 Correct 107 ms 66772 KB Output is correct
27 Correct 270 ms 102624 KB Output is correct
28 Correct 286 ms 76912 KB Output is correct
29 Correct 622 ms 84976 KB Output is correct
30 Correct 377 ms 79072 KB Output is correct
31 Correct 342 ms 77120 KB Output is correct
32 Correct 101 ms 66996 KB Output is correct
33 Correct 286 ms 76912 KB Output is correct
34 Correct 587 ms 85004 KB Output is correct
35 Correct 383 ms 78852 KB Output is correct
36 Correct 401 ms 78804 KB Output is correct
37 Correct 274 ms 77500 KB Output is correct
38 Correct 361 ms 106820 KB Output is correct