oj.uz

Submission #600981

# Submission time Handle Problem Language Result Execution time Memory
600981 2022-07-21T09:47:56 Z Lucpp Simurgh (IOI17_simurgh) C++17
30 / 100
 1290 ms 5236 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> g;
vector<int> good;

void calc(int i){
	int start = edges[i].first, goal = edges[i].second;
	queue<int> q;
	q.push(start);
	vector<bool> vis(n);
	vis[start] = true;
	vector<pair<int, int>> last(n);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto [v, ind] : g[u]){
			if(ind == i) continue;
			if(!vis[v]){
				vis[v] = true;
				q.push(v);
				last[v] = {u, ind};
			}
		}
	}
	if(!vis[goal]){ // bridge
		good[i] = true;
		return;
	}
	vector<int> cycle;
	vector<int> inCycle(m);
	int u = goal;
	while(u != start){
		inCycle[last[u].second] = true;
		cycle.push_back(last[u].second);
		u = last[u].first;
	}
	inCycle[i] = true;
	cycle.push_back(i);
	vector<int> forest;
	for(u = 0; u < n; u++){
		if(u != start){
			int e = last[u].second;
			if(!inCycle[e]) forest.push_back(e);
		}
	}
	int c = (int)cycle.size();
	vector<int> ans(c);
	for(int j = 0; j < c; j++){
		vector<int> v;
		for(int k = 0; k < c; k++){
			if(k != j) v.push_back(cycle[k]);
		}
		for(int e : forest) v.push_back(e);
		ans[j] = count_common_roads(v);
	}
	for(int j = 0; j < c; j++){
		int ma = 0;
		for(int k = 0; k < c; k++){
			if(j != k) ma = max(ma, ans[k]);
		}
		good[cycle[j]] = ma > ans[j];
	}
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
	n = n_;
	m = (int)u.size();
	g.resize(n);
	for(int i = 0; i < m; i++){
		edges.emplace_back(u[i], v[i]);
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}
	good.resize(m, -1);
	for(int i = 0; i < m; i++){
		if(good[i] == -1){
			calc(i);
		}
	}
	vector<int> r;
	for(int i = 0; i < m; i++) if(good[i] == 1) r.push_back(i);
	return r;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 224 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 224 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 8 ms 340 KB correct
15 Correct 8 ms 340 KB correct
16 Correct 8 ms 388 KB correct
17 Correct 7 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 7 ms 340 KB correct
20 Correct 7 ms 340 KB correct
21 Correct 6 ms 376 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 4 ms 340 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 300 KB correct
26 Correct 12 ms 300 KB correct
27 Correct 4 ms 300 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 3 ms 340 KB correct
33 Correct 4 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 224 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 8 ms 340 KB correct
15 Correct 8 ms 340 KB correct
16 Correct 8 ms 388 KB correct
17 Correct 7 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 7 ms 340 KB correct
20 Correct 7 ms 340 KB correct
21 Correct 6 ms 376 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 4 ms 340 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 300 KB correct
26 Correct 12 ms 300 KB correct
27 Correct 4 ms 300 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 3 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 1095 ms 2000 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 212 KB correct
3 Incorrect 1290 ms 5236 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 304 KB correct
11 Correct 1 ms 224 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 8 ms 340 KB correct
15 Correct 8 ms 340 KB correct
16 Correct 8 ms 388 KB correct
17 Correct 7 ms 340 KB correct
18 Correct 2 ms 212 KB correct
19 Correct 7 ms 340 KB correct
20 Correct 7 ms 340 KB correct
21 Correct 6 ms 376 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 4 ms 340 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 300 KB correct
26 Correct 12 ms 300 KB correct
27 Correct 4 ms 300 KB correct
28 Correct 2 ms 212 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 3 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 1095 ms 2000 KB WA in grader: NO
35 Halted 0 ms 0 KB -