oj.uz

Submission #615562

# Submission time Handle Problem Language Result Execution time Memory
615562 2022-07-31T10:40:30 Z HamletPetrosyan Keys (IOI21_keys) C++17
9 / 100
 98 ms 21612 KB 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pii pair<int, int>
#define fr first
#define sc second

const int N = 3e2 + 5;

vector<pii> g[N];
int cnt[N][N], a[N];
int color[N];

int dfs(int v, int col){
	int ret = 1;
	color[v] = col;
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i].fr;
		if(color[to] == col) continue;
		ret += dfs(to, col);
	}
	return ret;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(len(r), 0);
	for(int i = 0; i < len(u); i++){
		g[u[i]].add({v[i], c[i]}); cnt[u[i]][c[i]]++;
		g[v[i]].add({u[i], c[i]}); cnt[v[i]][c[i]]++;
	}
	bool o = false;
	for(int i = 0; i < len(r); i++){
		if(cnt[i][r[i]] == 0){
			o = true;
			ans[i] = 1;
		}
	}
	if(o){
//		cout << "o" << endl;
		return ans;
	}
	ans.resize(len(r), 0);
	int mn = 10000009;
	for(int i = 0; i < len(r); i++){
		a[i] = dfs(i, i + 1);
		mn = min(a[i], mn);
	}
	for(int i = 0; i < len(r); i++){
		ans[i] = (a[i] == mn);
	}
	return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Incorrect 1 ms 444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Incorrect 1 ms 444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Runtime error 98 ms 21612 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Incorrect 1 ms 444 KB Output isn't correct
16 Halted 0 ms 0 KB -