oj.uz

Submission #293121

# Submission time Handle Problem Language Result Execution time Memory
293121 2020-09-07T16:36:18 Z amoo_safar Simurgh (IOI17_simurgh) C++17
30 / 100
 3000 ms 124204 KB 
#include "simurgh.h"

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 500 + 10;

vector<pii> G[N], H[N];
int mk[N], E[N], par[N], dep[N];

vector<int> R;

void DFS1(int u, int d = 0){
	mk[u] = 1;
	dep[u] = d;
	for(auto [adj, id] : G[u]){
		if(!mk[adj]){
			R.pb(id);
			par[adj] = u;
			DFS1(adj, d + 1);
			E[adj] = id;
			//cerr << "^ " << u << ' ' << adj << '\n';
		}
	}
}
ll f;
map<pii, int> mp;
int Ask(int rm, int is){
	if(mp.count({rm, is})) return mp[{rm, is}];
	vector<int> R2 = R;
	for(auto &x : R2) if(x == rm) x = is;
	mp[{rm, is}] = count_common_roads(R2);
	//cerr << "Ask " << rm << ' ' << is << ' ' << mp[{rm, is}] << '\n';
	return mp[{rm, is}];
}

int sta[N * N];

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> r(n - 1);
	int m = u.size();
	for(int i = 0; i < m; i++){
		G[u[i]].pb({v[i], i});
		G[v[i]].pb({u[i], i});
	}
	DFS1(0, 0);
	f = count_common_roads(R);
	E[0] = -1;
	par[0] = -1;
	//cerr << "F : " << f << '\n';

	vector<int> X;
	for(int i = 0; i < m; i++){
		if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
		if(E[v[i]] == i) continue;
		X.clear();
		int nw = v[i];
		////cerr << '\n';
		while(nw != u[i]){
			////cerr << "# " << nw << '\n';
			X.pb(E[nw]);
			nw = par[nw];
		}
		//cerr << "& " << u[i] << ' ' << v[i] << '\n';
		//cerr << "!! ";
			//cerr << x << ' ';
		//cerr << '\n';

		int mn = f;
		bool flg = false;
		int res;
		//cerr << "MTF : " << f << '\n';
		for(auto x : X){
			if(sta[x] && flg){
				if(sta[x] == 2){
					mn = min(mn, res);
					mp[{x, i}] = res;
				} else {
					mp[{x, i}] = res + 1;
					mn = min(mn, res + 1);
				}
				continue;
			}
			if(sta[x] == 1){
				mn = min(mn, Ask(x, i));
				res = Ask(x, i) - 1;
				flg = true;
			} else if(sta[x] == 2){
				mn = min(mn, Ask(x, i));
				res = Ask(x, i);
				flg = true;
			} else {
				mn = min(mn, Ask(x, i));
			}
		}
		
		//cerr << "mn : " << mn << '\n';

		bool f2 = (f != mn);
		for(auto x : X) if(mn != Ask(x, i)) f2 = true;
		if(f2){
			if(f == mn) sta[i] = 2;
			else sta[i] = 1;
			for(auto x : X){
				if(sta[x] == 0){
					if(Ask(x, i) == mn) sta[x] = 2;
					else sta[x] = 1;
				}
			}
		} else {
			sta[i] = 1;
			for(auto x : X) sta[x] = 1;
		}

		//for(int j = 0; j < m; j++) //cerr << sta[j];
		//cerr << '\n';
	}
	vector<int> res;
	for(int i = 0; i < m; i++) if(sta[i] != 1) res.pb(i);
	//for(auto x : res)
		//cerr << "% " << x << '\n';

	assert(((int) res.size()) == n - 1);
	return res;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 0 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 15 ms 1776 KB correct
15 Correct 14 ms 1664 KB correct
16 Correct 15 ms 1664 KB correct
17 Correct 11 ms 1536 KB correct
18 Correct 4 ms 768 KB correct
19 Correct 13 ms 1536 KB correct
20 Correct 11 ms 1408 KB correct
21 Correct 10 ms 1408 KB correct
22 Correct 6 ms 896 KB correct
23 Correct 4 ms 768 KB correct
24 Correct 4 ms 768 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 4 ms 640 KB correct
27 Correct 4 ms 768 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 6 ms 1024 KB correct
31 Correct 7 ms 1024 KB correct
32 Correct 6 ms 1024 KB correct
33 Correct 7 ms 1024 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 0 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 15 ms 1776 KB correct
15 Correct 14 ms 1664 KB correct
16 Correct 15 ms 1664 KB correct
17 Correct 11 ms 1536 KB correct
18 Correct 4 ms 768 KB correct
19 Correct 13 ms 1536 KB correct
20 Correct 11 ms 1408 KB correct
21 Correct 10 ms 1408 KB correct
22 Correct 6 ms 896 KB correct
23 Correct 4 ms 768 KB correct
24 Correct 4 ms 768 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 4 ms 640 KB correct
27 Correct 4 ms 768 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 6 ms 1024 KB correct
31 Correct 7 ms 1024 KB correct
32 Correct 6 ms 1024 KB correct
33 Correct 7 ms 1024 KB correct
34 Execution timed out 3073 ms 124204 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Correct 1 ms 384 KB correct
3 Incorrect 2988 ms 101964 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 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 0 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 0 ms 384 KB correct
7 Correct 0 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 15 ms 1776 KB correct
15 Correct 14 ms 1664 KB correct
16 Correct 15 ms 1664 KB correct
17 Correct 11 ms 1536 KB correct
18 Correct 4 ms 768 KB correct
19 Correct 13 ms 1536 KB correct
20 Correct 11 ms 1408 KB correct
21 Correct 10 ms 1408 KB correct
22 Correct 6 ms 896 KB correct
23 Correct 4 ms 768 KB correct
24 Correct 4 ms 768 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 4 ms 640 KB correct
27 Correct 4 ms 768 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 6 ms 1024 KB correct
31 Correct 7 ms 1024 KB correct
32 Correct 6 ms 1024 KB correct
33 Correct 7 ms 1024 KB correct
34 Execution timed out 3073 ms 124204 KB Time limit exceeded
35 Halted 0 ms 0 KB -