oj.uz

답안 #97317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97317 2019-02-15T04:51:26 Z E869120 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 31080 KB 
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
	public:
	vector<int> par;
	
	void init(int size_) {
		par.resize(size_, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u != v) par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

int N, M, Q, X[1 << 18], Y[1 << 18], S[1 << 18], E[1 << 18], L[1 << 18], R[1 << 18], dp[1 << 18][2];
vector<int> G[1 << 18];

vector<int> check_validity (int NN, vector<int> XX, vector<int> YY, vector<int> SS, vector<int> EE, vector<int> LL, vector<int> RR) {
	// ------------------------------- 1. Input Data -------------------------------------
	N = NN; M = XX.size(); Q = SS.size();
	for (int i = 0; i < M; i++) X[i] = XX[i];
	for (int i = 0; i < M; i++) Y[i] = YY[i];
	for (int i = 0; i < Q; i++) S[i] = SS[i];
	for (int i = 0; i < Q; i++) E[i] = EE[i];
	for (int i = 0; i < Q; i++) L[i] = LL[i];
	for (int i = 0; i < Q; i++) R[i] = RR[i];
	for (int i = 0; i < M; i++) { if (X[i] < Y[i]) swap(X[i], Y[i]); }
	
	// ------------------------------- 2. Make Tree --------------------------------------
	vector<pair<int, int>> vec;
	for (int i = 0; i < M; i++) vec.push_back(make_pair(X[i], -Y[i]));
	sort(vec.begin(), vec.end());
	
	UnionFind UF; UF.init(N);
	for (int i = 0; i < vec.size(); i++) {
		if (UF.same(vec[i].first, -vec[i].second) == false) {
			G[vec[i].first].push_back(-vec[i].second);
			G[-vec[i].second].push_back(vec[i].first);
			UF.unite(vec[i].first, -vec[i].second);
		}
	}
	
	// ----------------------- 3. Calculate (15-points solution) ------------------------
	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; }
		
		queue<pair<int, int>> que; dp[S[i]][0] = 1; que.push(make_pair(S[i], 0));
		
		while (!que.empty()) {
			int pos1 = que.front().first, pos2 = que.front().second; que.pop();
			if (L[i] <= pos1 && pos1 <= R[i] && dp[pos1][1] == 0 && pos2 == 0) {
				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] == 0) { 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:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
werewolf.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[pos1].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4033 ms 31080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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