Submission #97315

#	Time	Username	Problem	Language	Result	Execution time	Memory
97315		E869120	늑대인간 (IOI18_werewolf)	C++14	49 / 100	1351 ms	84772 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51