oj.uz

Submission #73499

# Submission time Handle Problem Language Result Execution time Memory
73499 2018-08-28T11:00:36 Z SmsS Simurgh (IOI17_simurgh) C++14
0 / 100
 4 ms 636 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "simurgh.h"

const int maxn = 510;
int adj[maxn][maxn];
bool seen[maxn];
bool burn[maxn];
int s[maxn*maxn/2];
int h[maxn];
int par[maxn];
vector<int> res;
bool sc = 0;
int cur;
int n;

void dfs(int root){
	seen[root] = 1;
//	cout << root << endl;
	for2(i,0,n) if(adj[i][root] != -1){

		if(!seen[i]){
			h[i] = h[root]+1;
			par[i] = root;
			if(!sc)res.pb(adj[i][root]);
//			cout << root << ' ' << i << endl;
			dfs(i);
		}else if(sc && h[i] > h[root]+1){
//			cout << i << ' ' << root << endl;
			int x = i;
			while(x != root){
				int y = par[x];
				if(s[adj[x][y]]){
					int t = 0;
					for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
					res[t] = adj[i][root];
					if(count_common_roads(res) == cur-(s[adj[x][y]]==2)) s[adj[i][root]] = 1;
					else s[adj[i][root]] = 2;
					res[t] = adj[x][y];
					break;
				}
				x = y;
			}
//			cout << s[adj[i][root]] << ' ' << root << ' ' << i << endl;
			if(!s[adj[i][root]]){
				int mx = 0;
				vector<int> c;
				x = i;
				while(x != root){
					int y = par[x];
					int t = 0;
					for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
					res[t] = adj[i][root];
					c.pb(count_common_roads(res));
					mx = max(mx,c.back());
					res[t] = adj[x][y];
					x = y;
				}
				int cnt = 0;
				x = i;
				while(x != root){
					int y = par[x];
					if(c[cnt] != mx){
						s[adj[x][y]] = 2;
					}else s[adj[x][y]] = 1;
					cnt++;
					x = y;
				}
				if(cur != mx){
					s[adj[root][i]] = 2;
				}else s[adj[root][i]] = 1;
			}
		}
	}
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	n = N;
	for2(i,0,n) for2(j,0,n) adj[i][j] = -1;
	for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
	par[0] = -1;
	dfs(0);
	cur = count_common_roads(res);
	sc = 1;
	fill(seen,seen+n,0);
	dfs(0);
//	for2(i,0,m) cout << s[i] << endl;
	for2(i,0,m) if(!s[i]) s[i] = 2;
	res.clear();
	for2(i,0,m) if(s[i] == 2) res.pb(i);
	return res;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

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