oj.uz

Submission #302640

# Submission time Handle Problem Language Result Execution time Memory
302640 2020-09-19T00:35:56 Z errorgorn Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 199544 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){
			int *arr=nxt[layer][g[x]&15];
			rep(y,0,n) node[y]=arr[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 6 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 8 ms 7424 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Correct 26 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 6 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 8 ms 7424 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Correct 26 ms 15224 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 63 ms 34168 KB Output is correct
12 Correct 141 ms 72824 KB Output is correct
13 Correct 207 ms 115704 KB Output is correct
14 Correct 375 ms 190332 KB Output is correct
15 Correct 387 ms 198008 KB Output is correct
16 Correct 371 ms 181368 KB Output is correct
17 Correct 356 ms 180984 KB Output is correct
18 Correct 141 ms 72824 KB Output is correct
19 Correct 364 ms 190200 KB Output is correct
20 Correct 386 ms 197880 KB Output is correct
21 Correct 377 ms 181452 KB Output is correct
22 Correct 358 ms 180984 KB Output is correct
23 Correct 418 ms 199544 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 4992 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 6272 KB Output is correct
9 Correct 26 ms 15224 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 63 ms 34168 KB Output is correct
12 Correct 141 ms 72824 KB Output is correct
13 Correct 207 ms 115704 KB Output is correct
14 Correct 375 ms 190332 KB Output is correct
15 Correct 387 ms 198008 KB Output is correct
16 Correct 371 ms 181368 KB Output is correct
17 Correct 356 ms 180984 KB Output is correct
18 Correct 141 ms 72824 KB Output is correct
19 Correct 364 ms 190200 KB Output is correct
20 Correct 386 ms 197880 KB Output is correct
21 Correct 377 ms 181452 KB Output is correct
22 Correct 358 ms 180984 KB Output is correct
23 Correct 418 ms 199544 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 639 ms 34284 KB Output is correct
26 Correct 1187 ms 72952 KB Output is correct
27 Correct 2450 ms 115836 KB Output is correct
28 Execution timed out 5046 ms 190328 KB Time limit exceeded
29 Halted 0 ms 0 KB -