oj.uz

Submission #302633

# Submission time Handle Problem Language Result Execution time Memory
302633 2020-09-19T00:09:09 Z errorgorn Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 199160 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)-((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);
	}
}

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 5 ms 5888 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 6 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 8 ms 7424 KB Output is correct
7 Correct 4 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 5 ms 5888 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 6 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 8 ms 7424 KB Output is correct
7 Correct 4 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 4992 KB Output is correct
11 Correct 63 ms 34040 KB Output is correct
12 Correct 149 ms 72700 KB Output is correct
13 Correct 210 ms 115396 KB Output is correct
14 Correct 385 ms 189688 KB Output is correct
15 Correct 404 ms 197332 KB Output is correct
16 Correct 405 ms 181116 KB Output is correct
17 Correct 368 ms 180900 KB Output is correct
18 Correct 148 ms 72696 KB Output is correct
19 Correct 394 ms 189816 KB Output is correct
20 Correct 409 ms 197368 KB Output is correct
21 Correct 397 ms 180984 KB Output is correct
22 Correct 370 ms 180600 KB Output is correct
23 Correct 458 ms 199160 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 6 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 8 ms 7424 KB Output is correct
7 Correct 4 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 4992 KB Output is correct
11 Correct 63 ms 34040 KB Output is correct
12 Correct 149 ms 72700 KB Output is correct
13 Correct 210 ms 115396 KB Output is correct
14 Correct 385 ms 189688 KB Output is correct
15 Correct 404 ms 197332 KB Output is correct
16 Correct 405 ms 181116 KB Output is correct
17 Correct 368 ms 180900 KB Output is correct
18 Correct 148 ms 72696 KB Output is correct
19 Correct 394 ms 189816 KB Output is correct
20 Correct 409 ms 197368 KB Output is correct
21 Correct 397 ms 180984 KB Output is correct
22 Correct 370 ms 180600 KB Output is correct
23 Correct 458 ms 199160 KB Output is correct
24 Correct 8 ms 4992 KB Output is correct
25 Correct 2176 ms 34112 KB Output is correct
26 Correct 4396 ms 72780 KB Output is correct
27 Correct 3666 ms 115576 KB Output is correct
28 Execution timed out 5031 ms 189816 KB Time limit exceeded
29 Halted 0 ms 0 KB -