oj.uz

Submission #85354

# Submission time Handle Problem Language Result Execution time Memory
85354 2018-11-19T12:25:57 Z SirCeness Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 36488 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 = (visited[e] == 1) ? 1 : 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 616 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 273 ms 1136 KB Output is correct
11 Correct 130 ms 1244 KB Output is correct
12 Correct 23 ms 1556 KB Output is correct
13 Correct 228 ms 1556 KB Output is correct
14 Correct 153 ms 1580 KB Output is correct
15 Correct 472 ms 2000 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4021 ms 36488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 616 KB Output is correct
10 Correct 273 ms 1136 KB Output is correct
11 Correct 130 ms 1244 KB Output is correct
12 Correct 23 ms 1556 KB Output is correct
13 Correct 228 ms 1556 KB Output is correct
14 Correct 153 ms 1580 KB Output is correct
15 Correct 472 ms 2000 KB Output is correct
16 Execution timed out 4021 ms 36488 KB Time limit exceeded
17 Halted 0 ms 0 KB -