oj.uz

답안 #302638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302638 2020-09-19T00:25:08 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){
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 7552 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 7552 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 61 ms 34168 KB Output is correct
12 Correct 144 ms 72824 KB Output is correct
13 Correct 213 ms 115704 KB Output is correct
14 Correct 364 ms 190200 KB Output is correct
15 Correct 382 ms 197880 KB Output is correct
16 Correct 378 ms 181368 KB Output is correct
17 Correct 347 ms 181052 KB Output is correct
18 Correct 143 ms 72952 KB Output is correct
19 Correct 367 ms 190200 KB Output is correct
20 Correct 381 ms 197968 KB Output is correct
21 Correct 380 ms 181368 KB Output is correct
22 Correct 351 ms 180984 KB Output is correct
23 Correct 416 ms 199672 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 7552 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 61 ms 34168 KB Output is correct
12 Correct 144 ms 72824 KB Output is correct
13 Correct 213 ms 115704 KB Output is correct
14 Correct 364 ms 190200 KB Output is correct
15 Correct 382 ms 197880 KB Output is correct
16 Correct 378 ms 181368 KB Output is correct
17 Correct 347 ms 181052 KB Output is correct
18 Correct 143 ms 72952 KB Output is correct
19 Correct 367 ms 190200 KB Output is correct
20 Correct 381 ms 197968 KB Output is correct
21 Correct 380 ms 181368 KB Output is correct
22 Correct 351 ms 180984 KB Output is correct
23 Correct 416 ms 199672 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 644 ms 34168 KB Output is correct
26 Correct 1165 ms 72952 KB Output is correct
27 Correct 2462 ms 115832 KB Output is correct
28 Execution timed out 5111 ms 190140 KB Time limit exceeded
29 Halted 0 ms 0 KB -