oj.uz

답안 #236855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236855 2020-06-03T15:11:30 Z kostia244 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 23 ms 36864 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300500, mlg = 30;
int up[mlg][maxn], cnt[maxn];
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
	memset(cnt, 0, sizeof cnt);
	memset(up, -1, sizeof up);
	for(int i = 0; i < m; i++) {
		int f = R[i][0], t = R[i][1];
		//cout << f << " " << t << " " << i << '\n';
		if(cnt[f] < 2) up[0][2*f + cnt[f]] = 2*t + (cnt[t]==0);//, cout << 2*f + cnt[f] << " -- " << 2*t + (cnt[t]==0) << '\n';
		if(cnt[t] < 2) up[0][2*t + cnt[t]]= 2*f + (cnt[f]==0);//, cout << 2*t + cnt[t] << " -- " << 2*f + (cnt[f]==0) << '\n';
		cnt[f]++, cnt[t]++;
	}
	for(int i = 0; i < 2*n; i++) if(up[0][i] < 0) up[0][i] = up[0][i^1];
	for(int j = 0; j < 2*n; j++)
		for(int i = 1; i < mlg; i++)
			up[i][j] = up[i-1][up[i-1][j]];
	//for(int i = 0; i < 2*n; i++) cout << i << " = " << up[i][0] << "\n";
	for(int I = 0; I < Q; I++) {
		//cout << P << " " << G[I] << '\n';
		int ans = 0;
		for(int i = 0; i < 2*n; i+=2) cnt[i] = i;
		for(int i = 0; i < mlg; i++) {
			if(!((G[I]>>i)&1)) continue;
			for(int j = 0; j < 2*n; j+=2) {
				cnt[j] = up[i][cnt[j]];
			}
		}
		for(int i = 0; i < 2*n; i+=2) ans += cnt[i] == 2*P || cnt[i] == 2*P+1;
		answer(ans);
	}
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 36864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 36864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 36864 KB Output isn't correct
2 Halted 0 ms 0 KB -