oj.uz

Submission #446537

# Submission time Handle Problem Language Result Execution time Memory
446537 2021-07-22T10:48:29 Z MilosMilutinovic Werewolf (IOI18_werewolf) C++14
15 / 100
 321 ms 29060 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MX = 2e5 + 5;

int n, m, q;
vector<int> adj[MX];

bool was[MX][2];

void dfs1(int u, int l) {
	was[u][0] = true;
	for (int v : adj[u]) {
		if (!was[v][0] && v >= l) {
			dfs1(v, l);
		}
	}	
}

void dfs2(int u, int r) {
	was[u][1] = true;
	for (int v : adj[u]) {
		if (!was[v][1] && v <= r) {
			dfs2(v, r);
		}
	}
}

void cl() {
	for (int i = 0; i < n; i++) {
		was[i][0] = false;
		was[i][1] = false;
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N; m = (int) X.size(); q = (int) L.size();
	for (int i = 0; i < m; i++) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	if (n <= 3000 && m <= 6000 && q <= 3000) {
		vector<int> ans(q);
		for (int i = 0; i < q; i++) {
			cl(); dfs1(S[i], L[i]); dfs2(E[i], R[i]);
			for (int j = 0; j < n; j++) 
				if (was[j][0] && was[j][1]) ans[i] = 1;
		}
		return ans;
	}
	vector<int> ans(1, -1);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4912 KB Output is correct
6 Correct 3 ms 4996 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4912 KB Output is correct
6 Correct 3 ms 4996 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 296 ms 5360 KB Output is correct
11 Correct 186 ms 5340 KB Output is correct
12 Correct 32 ms 5324 KB Output is correct
13 Correct 321 ms 5364 KB Output is correct
14 Correct 220 ms 5344 KB Output is correct
15 Correct 260 ms 5484 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 29060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4912 KB Output is correct
6 Correct 3 ms 4996 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 296 ms 5360 KB Output is correct
11 Correct 186 ms 5340 KB Output is correct
12 Correct 32 ms 5324 KB Output is correct
13 Correct 321 ms 5364 KB Output is correct
14 Correct 220 ms 5344 KB Output is correct
15 Correct 260 ms 5484 KB Output is correct
16 Incorrect 234 ms 29060 KB Output isn't correct
17 Halted 0 ms 0 KB -