oj.uz

답안 #97315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97315 2019-02-15T04:13:24 Z E869120 늑대인간 (IOI18_werewolf) C++14
49 / 100
 1351 ms 84772 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

class RangedTree {
	public:
	
	vector<int> dat[22], U; int ty, size_;
	
	void init(int N, vector<int>T, int typ) {
		size_ = N;
		for (int i = 0; i < 22; i++) dat[i].resize(N + 2, 0);
		for (int i = 0; i < N; i++) dat[0][i] = T[i];
		for (int i = 0; i < 21; i++) {
			for (int j = 0; j < N; j++) {
				if (j + (1 << i) >= N) dat[i + 1][j] = dat[i][j];
				else {
					if (typ == 1) dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
					if (typ == 2) dat[i + 1][j] = max(dat[i][j], dat[i][j + (1 << i)]);
				}
			}
		}
		ty = typ;
		U.resize(N + 2, 0);
		for (int i = 0; i < 21; i++) {
			for (int j = (1 << i); j < (2 << i); j++) {
				if (j < (int)U.size()) U[j] = i;
			}
		}
	}
	int query(int cl, int cr) {
		cr++; if (cr > size_) cr = size_;
		int lens = cr - cl;
		if (ty == 1) return min(dat[U[lens]][cl], dat[U[lens]][cr - (1 << U[lens])]);
		if (ty == 2) return max(dat[U[lens]][cl], dat[U[lens]][cr - (1 << U[lens])]);
		return -1;
	}
};

int N, M, Q, dp[5009][2], I[200009], J[200009], Order[200009]; vector<int>G[200009];
RangedTree Z[2]; bool used[200009];

pair<int, int> calc(int ty, int pos, int lim) {
	if (ty == 1) {
		int L1 = 0, R1 = pos + 1, M1, T1 = pos;
		for (int i = 0; i < 20; i++) {
			M1 = (L1 + R1) / 2;
			int B = Z[0].query(M1, pos);
			if (B >= lim) { R1 = M1; T1 = min(T1, M1); }
			else { L1 = M1; }
		}
		int L2 = pos, R2 = N, M2, T2 = pos;
		for (int i = 0; i < 20; i++) {
			M2 = (L2 + R2) / 2;
			int B = Z[0].query(pos, M2);
			if (B >= lim) { L2 = M2; T2 = max(T2, M2); }
			else { R2 = M2; } 
		}
		return make_pair(T1, T2);
	}
	if (ty == 2) {
		int L1 = 0, R1 = pos + 1, M1, T1 = pos;
		for (int i = 0; i < 20; i++) {
			M1 = (L1 + R1) / 2;
			int B = Z[1].query(M1, pos); //cout << "max [" << M1 << ", " << pos << "] = " << B << endl;
			if (B <= lim) { R1 = M1; T1 = min(T1, M1); }
			else { L1 = M1; }
		}
		int L2 = pos, R2 = N, M2, T2 = pos;
		for (int i = 0; i < 20; i++) {
			M2 = (L2 + R2) / 2;
			int B = Z[1].query(pos, M2); //cout << "max [" << pos << ", " << M2 << "] = " << B << endl;
			if (B <= lim) { L2 = M2; T2 = max(T2, M2); }
			else { R2 = M2; } 
		}
		return make_pair(T1, T2);
	}
}

vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = NN; M = X.size(); Q = S.size();
	for (int i = 0; i < M; i++) { G[X[i]].push_back(Y[i]); G[Y[i]].push_back(X[i]); }
	
	if (!(N <= 3000 && M <= 6000 && Q <= 3000)){
		// For subtask 3
		int cx = -1; for (int i = 0; i < N; i++) { if (G[i].size() == 1) cx = i; }
		int cntv = 0; used[cx] = true; I[cntv] = cx; cntv++;
		
		while (true) {
			int cp = -1; for (int i = 0; i < G[cx].size(); i++) { if (used[G[cx][i]]==false) cp=G[cx][i]; }
			if (cp == -1) break;
			I[cntv] = cp; cx = cp; cntv++; used[cx]=true;
		}
		
		vector<int> V; for (int i = 0; i < cntv; i++) { V.push_back(I[i]); Order[I[i]] = i; }
		Z[0].init(N, V, 1);
		Z[1].init(N, V, 2);
		
		vector<int>ans;
		for (int i = 0; i < Q; i++) {
			//cout << "Start = " << Order[S[i]] << ", Goal = " << Order[E[i]] << endl;
			pair<int, int> A1 = calc(1, Order[S[i]], L[i]);
			pair<int, int> A2 = calc(2, Order[E[i]], R[i]);
			pair<int, int> A3 = make_pair(max(A1.first, A2.first), min(A1.second, A2.second));
			
			//cout << "Human = [" << A1.first << ", " << A1.second << "] , Wolf = [" << A2.first << ", " << A2.second << "]" << endl;
			
			if (A3.first <= A3.second) ans.push_back(1);
			else ans.push_back(0);
		}
		return ans;
	}
	else {
		// For subtask 1, 2
		vector<int>ans;
		
		for (int i = 0; i < Q; i++) {
			for (int j = 0; j <= N; j++) { dp[j][0] = 0; dp[j][1] = 0; }
			dp[S[i]][0] = 1; queue<pair<int, int>> que; que.push(make_pair(S[i], 0));
			
			while(!que.empty()){
				int pos1 = que.front().first, pos2 = que.front().second; que.pop();
				
				if (pos2 == 0 && dp[pos1][1] == 0 && L[i] <= pos1 && pos1 <= R[i]) {
					dp[pos1][1] = 1;
					que.push(make_pair(pos1, 1));
				}
				
				for (int j = 0; j < G[pos1].size(); j++) {
					int to = G[pos1][j];
					if (pos2 == 0 && to < L[i]) continue;
					if (pos2 == 1 && R[i] < to) continue;
					if (dp[to][pos2] == 1) continue;
					dp[to][pos2] = 1;
					que.push(make_pair(to, pos2));
				}
			}
			
			ans.push_back(dp[E[i]][1]);
		}
		return ans;
	}
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:90:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    int cp = -1; for (int i = 0; i < G[cx].size(); i++) { if (used[G[cx][i]]==false) cp=G[cx][i]; }
                                 ~~^~~~~~~~~~~~~~
werewolf.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < G[pos1].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::pair<int, int> calc(int, int, int)':
werewolf.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 446 ms 5388 KB Output is correct
11 Correct 310 ms 5496 KB Output is correct
12 Correct 32 ms 5368 KB Output is correct
13 Correct 390 ms 5724 KB Output is correct
14 Correct 248 ms 5368 KB Output is correct
15 Correct 292 ms 5376 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1306 ms 61576 KB Output is correct
2 Correct 1226 ms 69780 KB Output is correct
3 Correct 1022 ms 69940 KB Output is correct
4 Correct 1351 ms 69980 KB Output is correct
5 Correct 1038 ms 69944 KB Output is correct
6 Correct 1130 ms 69948 KB Output is correct
7 Correct 1210 ms 69896 KB Output is correct
8 Correct 945 ms 69940 KB Output is correct
9 Correct 579 ms 69788 KB Output is correct
10 Correct 717 ms 69924 KB Output is correct
11 Correct 802 ms 69912 KB Output is correct
12 Correct 656 ms 70036 KB Output is correct
13 Correct 1185 ms 70012 KB Output is correct
14 Correct 1086 ms 69980 KB Output is correct
15 Correct 1008 ms 69980 KB Output is correct
16 Correct 1144 ms 69912 KB Output is correct
17 Correct 1109 ms 69980 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 446 ms 5388 KB Output is correct
11 Correct 310 ms 5496 KB Output is correct
12 Correct 32 ms 5368 KB Output is correct
13 Correct 390 ms 5724 KB Output is correct
14 Correct 248 ms 5368 KB Output is correct
15 Correct 292 ms 5376 KB Output is correct
16 Correct 1306 ms 61576 KB Output is correct
17 Correct 1226 ms 69780 KB Output is correct
18 Correct 1022 ms 69940 KB Output is correct
19 Correct 1351 ms 69980 KB Output is correct
20 Correct 1038 ms 69944 KB Output is correct
21 Correct 1130 ms 69948 KB Output is correct
22 Correct 1210 ms 69896 KB Output is correct
23 Correct 945 ms 69940 KB Output is correct
24 Correct 579 ms 69788 KB Output is correct
25 Correct 717 ms 69924 KB Output is correct
26 Correct 802 ms 69912 KB Output is correct
27 Correct 656 ms 70036 KB Output is correct
28 Correct 1185 ms 70012 KB Output is correct
29 Correct 1086 ms 69980 KB Output is correct
30 Correct 1008 ms 69980 KB Output is correct
31 Correct 1144 ms 69912 KB Output is correct
32 Correct 1109 ms 69980 KB Output is correct
33 Runtime error 358 ms 84772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -