oj.uz

Submission #790658

# Submission time Handle Problem Language Result Execution time Memory
790658 2023-07-23T04:47:59 Z peteza Simurgh (IOI17_simurgh) C++14
13 / 100
 64 ms 3384 KB 
#include "simurgh.h"
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using pii = pair<int, int>;

int tim[505], ct, ign;
bool vis[505];
vector<pii> adj[505];
vector<int> times[505];

void dfs(int x, vector<int> &to) {
	vis[x] = 1;
	for(pii e:adj[x]) {
		if(e.first == ign) {
			times[ct].push_back(e.second);
			continue;
		}
		if(vis[e.first]) continue;
		vis[e.first] = 1; tim[e.first] = ct;
		to.push_back(e.second);
		dfs(e.first, to);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	std::vector<int> r;
	int m = u.size();
	for(int i=0;i<m;i++) adj[u[i]].emplace_back(v[i], i), adj[v[i]].emplace_back(u[i], i);
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) times[j].clear();
		//with this node as the main node, generate a spanning tree ignoring this node
		ign = i;
		std::vector<int> toask;
		memset(vis, 0, sizeof vis); vis[i] = 1;
		memset(tim, -1, sizeof tim);
		for(int j=0;j<n;j++) {
			ct = j;
			if(i != j && !vis[j]) dfs(j, toask);
		}
		int cq = 0;
		//for(int j=0;j<n;j++) cout << tim[j] << ' '; cout << '\n';
		for(int ctime = 0;ctime<n;ctime++) {
			if(times[ctime].empty()) continue;
			for(int ktime=0;ktime<n;ktime++) {
				if(ktime == ctime) continue;
				for(int e:times[ktime]) toask.push_back(e);
			}
			std::vector<int> inans;
			int mx = -1;
			for(int e:times[ctime]) {
				toask.push_back(e);
				if(cq++ >= 29000 || toask.size() != n-1) exit(1);
				int res = count_common_roads(toask);
				if(res >= mx) {
					if(res > mx) inans.clear();
					mx = res;
					inans.push_back(e);
				}
				toask.pop_back();
			}
			for(int ktime=0;ktime<n;ktime++) {
				if(ktime == ctime) continue;
				for(int e:times[ktime]) toask.pop_back();
			}
			for(int e:inans) r.push_back(e);
		}
	}
	sort(r.begin(), r.end());
	r.resize(unique(r.begin(), r.end())-r.begin());
	return r;
}

/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:54:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if(cq++ >= 29000 || toask.size() != n-1) exit(1);
      |                         ~~~~~~~~~~~~~^~~~~~
simurgh.cpp:65:13: warning: unused variable 'e' [-Wunused-variable]
   65 |     for(int e:times[ktime]) toask.pop_back();
      |             ^

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 0 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct

Subtask #2
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 0 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 340 KB correct
20 Correct 2 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
23 Halted 0 ms 0 KB -

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 0 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 340 KB correct
20 Correct 2 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Incorrect 64 ms 3384 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 0 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 340 KB correct
20 Correct 2 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
23 Halted 0 ms 0 KB -