oj.uz

Submission #302637

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

int node[150005];

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) node[y]=al[y][0];
		
		rep(layer,0,8){
			rep(y,0,n) node[y]=nxt[layer][g[x]&15][node[y]];
			g[x]>>=4;
		}
		
		rep(y,0,n) if (v[node[y]]==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 7 ms 6272 KB Output is correct
4 Correct 4 ms 4864 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 9 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 15232 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 4 ms 4864 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 9 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 15232 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 59 ms 34076 KB Output is correct
12 Correct 144 ms 72952 KB Output is correct
13 Correct 199 ms 115704 KB Output is correct
14 Correct 371 ms 190200 KB Output is correct
15 Correct 389 ms 197880 KB Output is correct
16 Correct 374 ms 181420 KB Output is correct
17 Correct 346 ms 180984 KB Output is correct
18 Correct 140 ms 72824 KB Output is correct
19 Correct 378 ms 190204 KB Output is correct
20 Correct 385 ms 197880 KB Output is correct
21 Correct 373 ms 181368 KB Output is correct
22 Correct 356 ms 181052 KB Output is correct
23 Correct 426 ms 199672 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 4 ms 4864 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 9 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 15232 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 59 ms 34076 KB Output is correct
12 Correct 144 ms 72952 KB Output is correct
13 Correct 199 ms 115704 KB Output is correct
14 Correct 371 ms 190200 KB Output is correct
15 Correct 389 ms 197880 KB Output is correct
16 Correct 374 ms 181420 KB Output is correct
17 Correct 346 ms 180984 KB Output is correct
18 Correct 140 ms 72824 KB Output is correct
19 Correct 378 ms 190204 KB Output is correct
20 Correct 385 ms 197880 KB Output is correct
21 Correct 373 ms 181368 KB Output is correct
22 Correct 356 ms 181052 KB Output is correct
23 Correct 426 ms 199672 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 757 ms 34424 KB Output is correct
26 Correct 1395 ms 72952 KB Output is correct
27 Correct 2771 ms 115768 KB Output is correct
28 Execution timed out 5067 ms 190200 KB Time limit exceeded
29 Halted 0 ms 0 KB -