oj.uz

Submission #799081

# Submission time Handle Problem Language Result Execution time Memory
799081 2023-07-31T09:31:55 Z LittleCube Simurgh (IOI17_simurgh) C++17
30 / 100
 86 ms 4004 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int vis[505], cc[505], base[505], out[505];
vector<pii> E[505];
vector<int> tree, ans;

void dfs(int u, int c)
{
	vis[u] = 1;
	cc[u] = c;
	for (auto [v, i] : E[u])
		if (!vis[v])
		{
			tree.emplace_back(i);
			dfs(v, c);
		}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
	int m = u.size();
	for (int i = 0; i < m; i++)
	{
		E[u[i]].emplace_back(pii(v[i], i));
		E[v[i]].emplace_back(pii(u[i], i));
	}
	for (int i = 0; i < n; i++)
	{
		tree.clear();
		for (int j = 0; j < n; j++)
			vis[j] = 0, base[j] = -1, out[j] = -1;
		vis[i] = 1;
		for (auto j = 0; j < n; j++)
			if (!vis[j])
				dfs(j, j);
		// check
		vector<tuple<int, int, int>> queries;
		for (auto [j, id] : E[i])
			out[cc[j]] = id;
		
		for (auto [j, id] : E[i])
		{
			vector<int> query = tree;
			for (int k = 0; k < n; k++)
				if (k != cc[j] && out[k] >= 0)
					query.emplace_back(out[k]);
			query.emplace_back(id);
			int res = count_common_roads(query);
			base[cc[j]] = max(base[cc[j]], res);
			queries.emplace_back(make_tuple(j, id, res));
		}
		for (auto [j, id, res] : queries)
			if (res == base[cc[j]])
			{
				ans.emplace_back(id);
			}
	}
	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 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 320 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 320 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 312 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 0 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 320 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 320 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 312 KB correct
14 Correct 2 ms 320 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 312 KB correct
19 Correct 2 ms 380 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 2 ms 316 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 1 ms 312 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 316 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 0 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 320 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 320 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 312 KB correct
14 Correct 2 ms 320 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 312 KB correct
19 Correct 2 ms 380 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 2 ms 316 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 1 ms 312 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 316 KB correct
34 Incorrect 86 ms 1544 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 212 KB correct
2 Correct 1 ms 212 KB correct
3 Incorrect 66 ms 4004 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 0 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 320 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 320 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 0 ms 312 KB correct
14 Correct 2 ms 320 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 312 KB correct
19 Correct 2 ms 380 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 2 ms 316 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 1 ms 312 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 316 KB correct
34 Incorrect 86 ms 1544 KB WA in grader: NO
35 Halted 0 ms 0 KB -