oj.uz

답안 #85351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85351 2018-11-19T12:20:42 Z SirCeness 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 40524 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
void dfsup(int node, list<int> *adj, int edge , int *visited){
	//cout << "dfsup(" << node << ")" << endl;
	visited[node] = 1;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (visited[*it]) continue;
		if (*it < edge) continue;
		dfsup(*it, adj, edge, visited);
	}
}
 
int dfsdown(int node, list<int> *adj, int edge, int *visited){
	//cout << "dfsdown(" << node << ")" << endl;
	visited[node] = 2;
	for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
		if (*it > edge) continue;
		if (visited[*it] == 1) return 1;
		if (visited[*it]) continue;
		if (dfsdown(*it, adj, edge, visited)) return 1;
	}
	return 0;
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	
	int Q = S.size();
	vector<int> A(Q);
	
	list<int> adj[N];
	for (int i = 0; i < (int)X.size(); i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	
	for (int i = 0; i < Q; i++){
		int l = L[i];
		int r = R[i];
		int s = S[i];
		int e = E[i];
		
		/*cout << "l: " << l;
		cout << " r: " << r;
		cout << " s: " << s;
		cout << " e: " << e;
		cout << endl;*/
		
		int visited[N];
		
		for (int q = 0; q < N; q++) visited[q] = 0;
		dfsup(s, adj, l, visited);
		int a = dfsdown(e, adj, r, visited);
		
		A[i] = a;
	}
	
	return A;
}
 
/*
	vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		A[i] = 0;
	}	
	return A;
*/

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 520 KB Output isn't correct
3 Halted 0 ms 0 KB -