oj.uz

Submission #73335

# Submission time Handle Problem Language Result Execution time Memory
73335 2018-08-28T07:33:44 Z Navick Simurgh (IOI17_simurgh) C++17
30 / 100
 144 ms 3452 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 510, maxE = maxN * maxN / 2;

int cmp[maxN], from[maxE], to[maxE], r, n;
bool mark[maxN];

vector <int> adj[maxN], ans, tree;
vector <int> edge[maxN];

void DFS(int v, int id)
{
	mark[v] = true;
	cmp[v] = id;

	for (auto i : adj[v])
	{
		int u = from[i] + to[i] - v;
		if(u == r || mark[u]) continue ;
		tree.pb(i);
		DFS(u, id);
	}
}

void solve(int v)
{
	memset(mark, 0, sizeof mark);
	r = v; 
	int sz = 0;
	tree.clear();
	
	for (int i=0; i<n; i++)
	{
		if(i == v || mark[i]) continue ;
		DFS(i, sz);
		sz ++;
	}

	for (auto i : adj[v])
	{
		int u = from[i] + to[i] - v;
		edge[cmp[u]].pb(i);
	}

	//cout << " FIRST " << v << " --> " << sz << endl;
	//for (auto x : tree) cout << x << ' '; cout << endl;

	for (int i=0; i<sz; i++)
		tree.pb(edge[i][0]);
	
	for (int i=0; i<sz; i++)
	{
		int td = edge[i].size(), mx = -1;
		vector <int> tmp;
		for (int j=0; j<td; j++)
		{
			tree[n - sz - 1 + i] = edge[i][j];
			int r = count_common_roads(tree);
			tmp.pb(r);
			mx = max(mx, r);
		}
		for (int j=0; j<td; j++) {
			//cout << edge[i][j] << " :: " << tmp[j] << endl;
			if(tmp[j] == mx) ans.pb(edge[i][j]);
		}
	}

	//cout << ans.size() << endl;

	for (int i=0; i<sz; i++) edge[i].clear();

}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
	int m = u.size(); n = _n;
	for (int i=0; i<m; i++)
	{
		from[i] = u[i];
		to[i] = v[i];
		adj[u[i]].pb(i);
		adj[v[i]].pb(i);
	}

	for (int i=0; i<n; i++) solve(i);

	sort(ans.begin(), ans.end());
	ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
	
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 3 ms 512 KB correct
5 Correct 2 ms 512 KB correct
6 Correct 2 ms 588 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 3 ms 588 KB correct
9 Correct 2 ms 588 KB correct
10 Correct 2 ms 588 KB correct
11 Correct 3 ms 588 KB correct
12 Correct 2 ms 588 KB correct
13 Correct 2 ms 612 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 3 ms 512 KB correct
5 Correct 2 ms 512 KB correct
6 Correct 2 ms 588 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 3 ms 588 KB correct
9 Correct 2 ms 588 KB correct
10 Correct 2 ms 588 KB correct
11 Correct 3 ms 588 KB correct
12 Correct 2 ms 588 KB correct
13 Correct 2 ms 612 KB correct
14 Correct 6 ms 612 KB correct
15 Correct 5 ms 612 KB correct
16 Correct 7 ms 616 KB correct
17 Correct 5 ms 616 KB correct
18 Correct 3 ms 616 KB correct
19 Correct 6 ms 740 KB correct
20 Correct 6 ms 740 KB correct
21 Correct 5 ms 740 KB correct
22 Correct 5 ms 740 KB correct
23 Correct 4 ms 740 KB correct
24 Correct 4 ms 740 KB correct
25 Correct 3 ms 740 KB correct
26 Correct 3 ms 740 KB correct
27 Correct 7 ms 740 KB correct
28 Correct 5 ms 740 KB correct
29 Correct 4 ms 740 KB correct
30 Correct 4 ms 740 KB correct
31 Correct 5 ms 740 KB correct
32 Correct 5 ms 740 KB correct
33 Correct 4 ms 740 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 3 ms 512 KB correct
5 Correct 2 ms 512 KB correct
6 Correct 2 ms 588 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 3 ms 588 KB correct
9 Correct 2 ms 588 KB correct
10 Correct 2 ms 588 KB correct
11 Correct 3 ms 588 KB correct
12 Correct 2 ms 588 KB correct
13 Correct 2 ms 612 KB correct
14 Correct 6 ms 612 KB correct
15 Correct 5 ms 612 KB correct
16 Correct 7 ms 616 KB correct
17 Correct 5 ms 616 KB correct
18 Correct 3 ms 616 KB correct
19 Correct 6 ms 740 KB correct
20 Correct 6 ms 740 KB correct
21 Correct 5 ms 740 KB correct
22 Correct 5 ms 740 KB correct
23 Correct 4 ms 740 KB correct
24 Correct 4 ms 740 KB correct
25 Correct 3 ms 740 KB correct
26 Correct 3 ms 740 KB correct
27 Correct 7 ms 740 KB correct
28 Correct 5 ms 740 KB correct
29 Correct 4 ms 740 KB correct
30 Correct 4 ms 740 KB correct
31 Correct 5 ms 740 KB correct
32 Correct 5 ms 740 KB correct
33 Correct 4 ms 740 KB correct
34 Incorrect 144 ms 1532 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1532 KB correct
2 Correct 2 ms 1532 KB correct
3 Incorrect 127 ms 3452 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 416 KB correct
4 Correct 3 ms 512 KB correct
5 Correct 2 ms 512 KB correct
6 Correct 2 ms 588 KB correct
7 Correct 2 ms 588 KB correct
8 Correct 3 ms 588 KB correct
9 Correct 2 ms 588 KB correct
10 Correct 2 ms 588 KB correct
11 Correct 3 ms 588 KB correct
12 Correct 2 ms 588 KB correct
13 Correct 2 ms 612 KB correct
14 Correct 6 ms 612 KB correct
15 Correct 5 ms 612 KB correct
16 Correct 7 ms 616 KB correct
17 Correct 5 ms 616 KB correct
18 Correct 3 ms 616 KB correct
19 Correct 6 ms 740 KB correct
20 Correct 6 ms 740 KB correct
21 Correct 5 ms 740 KB correct
22 Correct 5 ms 740 KB correct
23 Correct 4 ms 740 KB correct
24 Correct 4 ms 740 KB correct
25 Correct 3 ms 740 KB correct
26 Correct 3 ms 740 KB correct
27 Correct 7 ms 740 KB correct
28 Correct 5 ms 740 KB correct
29 Correct 4 ms 740 KB correct
30 Correct 4 ms 740 KB correct
31 Correct 5 ms 740 KB correct
32 Correct 5 ms 740 KB correct
33 Correct 4 ms 740 KB correct
34 Incorrect 144 ms 1532 KB WA in grader: NO
35 Halted 0 ms 0 KB -