oj.uz

Submission #302635

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#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;x!=end;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);
	}
}

Compilation message

garden.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
garden.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6016 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 4 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 22 ms 15104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6016 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 4 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 22 ms 15104 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 62 ms 34040 KB Output is correct
12 Correct 150 ms 72824 KB Output is correct
13 Correct 204 ms 115448 KB Output is correct
14 Correct 384 ms 189944 KB Output is correct
15 Correct 399 ms 197436 KB Output is correct
16 Correct 403 ms 181112 KB Output is correct
17 Correct 358 ms 180856 KB Output is correct
18 Correct 146 ms 72696 KB Output is correct
19 Correct 395 ms 189688 KB Output is correct
20 Correct 408 ms 197240 KB Output is correct
21 Correct 395 ms 180936 KB Output is correct
22 Correct 363 ms 180856 KB Output is correct
23 Correct 460 ms 198940 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6016 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 4 ms 4864 KB Output is correct
5 Correct 4 ms 4864 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 6 ms 6144 KB Output is correct
9 Correct 22 ms 15104 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 62 ms 34040 KB Output is correct
12 Correct 150 ms 72824 KB Output is correct
13 Correct 204 ms 115448 KB Output is correct
14 Correct 384 ms 189944 KB Output is correct
15 Correct 399 ms 197436 KB Output is correct
16 Correct 403 ms 181112 KB Output is correct
17 Correct 358 ms 180856 KB Output is correct
18 Correct 146 ms 72696 KB Output is correct
19 Correct 395 ms 189688 KB Output is correct
20 Correct 408 ms 197240 KB Output is correct
21 Correct 395 ms 180936 KB Output is correct
22 Correct 363 ms 180856 KB Output is correct
23 Correct 460 ms 198940 KB Output is correct
24 Correct 10 ms 4992 KB Output is correct
25 Correct 2097 ms 34108 KB Output is correct
26 Correct 4258 ms 72868 KB Output is correct
27 Correct 3449 ms 115552 KB Output is correct
28 Execution timed out 5032 ms 189960 KB Time limit exceeded
29 Halted 0 ms 0 KB -