oj.uz

Submission #73350

# Submission time Handle Problem Language Result Execution time Memory
73350 2018-08-28T07:46:29 Z Navick Simurgh (IOI17_simurgh) C++17
30 / 100
 170 ms 3436 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], good[maxE];
bool flag[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 ++;
	}
	
	memset(flag, 0, sizeof flag);

	for (auto i : adj[v])
	{
		int u = from[i] + to[i] - v;
		if(good[i] && !flag[cmp[u]]) edge[cmp[u]].pb(i), flag[cmp[u]] = true;
		else if(!good[i]) 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]);
	
	int last_ans = -1;
	for (int i=0; i<sz; i++)
	{
		int td = edge[i].size(), mx = -1;
		vector <int> tmp;

		if(last_ans != -1) tmp.pb(last_ans), mx = last_ans;
		else
		{
			int r = count_common_roads(tree);
			tmp.pb(r);
			mx = r;
			last_ans = r;
		}

		for (int j=1; j<td; j++)
		{
			tree[n - sz - 1 + i] = edge[i][j];
			int r = count_common_roads(tree);
			tmp.pb(r);
			mx = max(mx, r);
			last_ans = r;
		}
		for (int j=0; j<td; j++) {
			if(tmp[j] == mx) ans.pb(edge[i][j]), good[edge[i][j]] = true;
		}
	}

	//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 2 ms 416 KB correct
4 Correct 3 ms 492 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 3 ms 712 KB correct
8 Correct 3 ms 712 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 3 ms 712 KB correct
12 Correct 4 ms 712 KB correct
13 Correct 4 ms 712 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 2 ms 416 KB correct
4 Correct 3 ms 492 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 3 ms 712 KB correct
8 Correct 3 ms 712 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 3 ms 712 KB correct
12 Correct 4 ms 712 KB correct
13 Correct 4 ms 712 KB correct
14 Correct 7 ms 712 KB correct
15 Correct 8 ms 712 KB correct
16 Correct 5 ms 712 KB correct
17 Correct 6 ms 712 KB correct
18 Correct 5 ms 712 KB correct
19 Correct 6 ms 712 KB correct
20 Correct 5 ms 712 KB correct
21 Correct 4 ms 712 KB correct
22 Correct 5 ms 712 KB correct
23 Correct 4 ms 712 KB correct
24 Correct 5 ms 712 KB correct
25 Correct 2 ms 712 KB correct
26 Correct 5 ms 712 KB correct
27 Correct 4 ms 712 KB correct
28 Correct 3 ms 712 KB correct
29 Correct 2 ms 712 KB correct
30 Correct 4 ms 712 KB correct
31 Correct 4 ms 712 KB correct
32 Correct 3 ms 712 KB correct
33 Correct 6 ms 712 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 2 ms 416 KB correct
4 Correct 3 ms 492 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 3 ms 712 KB correct
8 Correct 3 ms 712 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 3 ms 712 KB correct
12 Correct 4 ms 712 KB correct
13 Correct 4 ms 712 KB correct
14 Correct 7 ms 712 KB correct
15 Correct 8 ms 712 KB correct
16 Correct 5 ms 712 KB correct
17 Correct 6 ms 712 KB correct
18 Correct 5 ms 712 KB correct
19 Correct 6 ms 712 KB correct
20 Correct 5 ms 712 KB correct
21 Correct 4 ms 712 KB correct
22 Correct 5 ms 712 KB correct
23 Correct 4 ms 712 KB correct
24 Correct 5 ms 712 KB correct
25 Correct 2 ms 712 KB correct
26 Correct 5 ms 712 KB correct
27 Correct 4 ms 712 KB correct
28 Correct 3 ms 712 KB correct
29 Correct 2 ms 712 KB correct
30 Correct 4 ms 712 KB correct
31 Correct 4 ms 712 KB correct
32 Correct 3 ms 712 KB correct
33 Correct 6 ms 712 KB correct
34 Incorrect 170 ms 1632 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 1632 KB correct
2 Correct 3 ms 1632 KB correct
3 Incorrect 136 ms 3436 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 2 ms 416 KB correct
4 Correct 3 ms 492 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 2 ms 584 KB correct
7 Correct 3 ms 712 KB correct
8 Correct 3 ms 712 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 3 ms 712 KB correct
12 Correct 4 ms 712 KB correct
13 Correct 4 ms 712 KB correct
14 Correct 7 ms 712 KB correct
15 Correct 8 ms 712 KB correct
16 Correct 5 ms 712 KB correct
17 Correct 6 ms 712 KB correct
18 Correct 5 ms 712 KB correct
19 Correct 6 ms 712 KB correct
20 Correct 5 ms 712 KB correct
21 Correct 4 ms 712 KB correct
22 Correct 5 ms 712 KB correct
23 Correct 4 ms 712 KB correct
24 Correct 5 ms 712 KB correct
25 Correct 2 ms 712 KB correct
26 Correct 5 ms 712 KB correct
27 Correct 4 ms 712 KB correct
28 Correct 3 ms 712 KB correct
29 Correct 2 ms 712 KB correct
30 Correct 4 ms 712 KB correct
31 Correct 4 ms 712 KB correct
32 Correct 3 ms 712 KB correct
33 Correct 6 ms 712 KB correct
34 Incorrect 170 ms 1632 KB WA in grader: NO
35 Halted 0 ms 0 KB -