oj.uz

Submission #302632

# Submission time Handle Problem Language Result Execution time Memory
302632 2020-09-19T00:06:32 Z errorgorn Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 199000 KB 
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,m,k,q;
vector<int> al[150005];
int v[300005];
int par[32][300005];

int nxt[8][16][300005];

void count_routes(int N, int M, int P, int R[][2], int Q, int g[]){
	n=N,m=M,k=P,q=Q;
	
	rep(x,0,m){
		al[R[x][0]].push_back(x*2);
		al[R[x][1]].push_back(x*2+1);
		
		v[x*2]=R[x][1];
		v[x*2+1]=R[x][0];
	}
	
	rep(x,0,m*2){
		if (sz(al[v[x]])==1 || (al[v[x]][0]>>1)!=(x>>1)) par[0][x]=al[v[x]][0];
		else par[0][x]=al[v[x]][1];
	}
	
	//rep(x,0,m*2) cout<<nxt[0][x]<<endl;
	
	rep(layer,0,31){
		rep(x,0,m*2){
			par[layer+1][x]=par[layer][par[layer][x]];
		}
	}
	
	rep(layer,0,8){
		rep(bm,0,16){
			rep(x,0,m*2){
				int curr=x;
				rep(bit,0,4) if (bm&(1<<bit)){
					curr=par[layer*4+bit][curr];
				}
				nxt[layer][bm][x]=curr;
			}
		}
	}
	
	rep(x,0,q){
		int ans=0;
		g[x]--;
		
		rep(y,0,n){
			int curr=al[y][0];
			int bm=g[x];		
			rep(layer,0,8){
				curr=nxt[layer][bm&15][curr];
				bm>>=4;
			}
			if (v[curr]==k) ans++;
		}
		
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 3 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 27 ms 15224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 3 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 27 ms 15224 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 71 ms 34040 KB Output is correct
12 Correct 162 ms 72696 KB Output is correct
13 Correct 237 ms 115320 KB Output is correct
14 Correct 430 ms 189816 KB Output is correct
15 Correct 454 ms 197368 KB Output is correct
16 Correct 435 ms 180984 KB Output is correct
17 Correct 404 ms 180920 KB Output is correct
18 Correct 164 ms 72828 KB Output is correct
19 Correct 442 ms 189816 KB Output is correct
20 Correct 456 ms 197368 KB Output is correct
21 Correct 427 ms 180984 KB Output is correct
22 Correct 415 ms 180728 KB Output is correct
23 Correct 507 ms 199000 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 3 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 27 ms 15224 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 71 ms 34040 KB Output is correct
12 Correct 162 ms 72696 KB Output is correct
13 Correct 237 ms 115320 KB Output is correct
14 Correct 430 ms 189816 KB Output is correct
15 Correct 454 ms 197368 KB Output is correct
16 Correct 435 ms 180984 KB Output is correct
17 Correct 404 ms 180920 KB Output is correct
18 Correct 164 ms 72828 KB Output is correct
19 Correct 442 ms 189816 KB Output is correct
20 Correct 456 ms 197368 KB Output is correct
21 Correct 427 ms 180984 KB Output is correct
22 Correct 415 ms 180728 KB Output is correct
23 Correct 507 ms 199000 KB Output is correct
24 Correct 10 ms 4992 KB Output is correct
25 Correct 2182 ms 34168 KB Output is correct
26 Correct 4534 ms 72924 KB Output is correct
27 Correct 3740 ms 116564 KB Output is correct
28 Execution timed out 5028 ms 191408 KB Time limit exceeded
29 Halted 0 ms 0 KB -