oj.uz

Submission #302627

# Submission time Handle Problem Language Result Execution time Memory
302627 2020-09-18T23:54:38 Z errorgorn Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 47992 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 nxt[30][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)) nxt[0][x]=al[v[x]][0];
		else nxt[0][x]=al[v[x]][1];
	}
	
	//rep(x,0,m*2) cout<<nxt[0][x]<<endl;
	
	rep(layer,0,29){
		rep(x,0,m*2){
			nxt[layer+1][x]=nxt[layer][nxt[layer][x]];
		}
	}
	
	rep(x,0,q){
		int ans=0;
		g[x]--;
		
		rep(y,0,n){
			int curr=al[y][0];			
			rep(layer,0,30) if (g[x]&(1<<layer)) curr=nxt[layer][curr];
			if (v[curr]==k) ans++;
		}
		
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 4 ms 4352 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 3 ms 4096 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 4 ms 4608 KB Output is correct
7 Correct 4 ms 4096 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 8 ms 6272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 4 ms 4352 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 3 ms 4096 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 4 ms 4608 KB Output is correct
7 Correct 4 ms 4096 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 8 ms 6272 KB Output is correct
10 Correct 3 ms 4096 KB Output is correct
11 Correct 22 ms 10624 KB Output is correct
12 Correct 45 ms 19064 KB Output is correct
13 Correct 58 ms 28924 KB Output is correct
14 Correct 125 ms 45688 KB Output is correct
15 Correct 132 ms 47480 KB Output is correct
16 Correct 130 ms 43128 KB Output is correct
17 Correct 112 ms 42872 KB Output is correct
18 Correct 49 ms 19064 KB Output is correct
19 Correct 133 ms 45688 KB Output is correct
20 Correct 135 ms 47480 KB Output is correct
21 Correct 132 ms 43000 KB Output is correct
22 Correct 122 ms 42744 KB Output is correct
23 Correct 148 ms 47992 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 4 ms 4352 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 3 ms 4096 KB Output is correct
5 Correct 3 ms 4096 KB Output is correct
6 Correct 4 ms 4608 KB Output is correct
7 Correct 4 ms 4096 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 8 ms 6272 KB Output is correct
10 Correct 3 ms 4096 KB Output is correct
11 Correct 22 ms 10624 KB Output is correct
12 Correct 45 ms 19064 KB Output is correct
13 Correct 58 ms 28924 KB Output is correct
14 Correct 125 ms 45688 KB Output is correct
15 Correct 132 ms 47480 KB Output is correct
16 Correct 130 ms 43128 KB Output is correct
17 Correct 112 ms 42872 KB Output is correct
18 Correct 49 ms 19064 KB Output is correct
19 Correct 133 ms 45688 KB Output is correct
20 Correct 135 ms 47480 KB Output is correct
21 Correct 132 ms 43000 KB Output is correct
22 Correct 122 ms 42744 KB Output is correct
23 Correct 148 ms 47992 KB Output is correct
24 Correct 13 ms 4096 KB Output is correct
25 Correct 4490 ms 10872 KB Output is correct
26 Execution timed out 5034 ms 19192 KB Time limit exceeded
27 Halted 0 ms 0 KB -