Submission #601052

#	Time	Username	Problem	Language	Result	Execution time	Memory
601052		Lucpp	Simurgh (IOI17_simurgh)	C++17	51 / 100	2600 ms	5248 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> g;
vector<int> good;

void calc(int i){
	int start = edges[i].first, goal = edges[i].second;
	queue<int> q;
	q.push(start);
	vector<bool> vis(n);
	vis[start] = true;
	vector<pair<int, int>> last(n);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto [v, ind] : g[u]){
			if(ind == i || good[ind] == 0) continue;
			if(!vis[v]){
				vis[v] = true;
				q.push(v);
				last[v] = {u, ind};
			}
		}
	}
	if(!vis[goal]){ // bridge
		good[i] = true;
		return;
	}
	vector<int> cycle;
	vector<int> inCycle(m);
	int u = goal;
	while(u != start){
		inCycle[last[u].second] = true;
		cycle.push_back(last[u].second);
		u = last[u].first;
	}
	inCycle[i] = true;
	cycle.push_back(i);
	vector<int> forest;
	for(u = 0; u < n; u++){
		if(u != start){
			int e = last[u].second;
			if(!inCycle[e]) forest.push_back(e);
		}
	}
	int c = (int)cycle.size();
	vector<int> ans(c);
	for(int j = 0; j < c; j++){
		if(good[cycle[j]] == 1) ans[j] = -1;
		else{
			vector<int> v;
			for(int k = 0; k < c; k++){
				if(k != j) v.push_back(cycle[k]);
			}
			for(int e : forest) v.push_back(e);
			ans[j] = count_common_roads(v);
		}
	}
	for(int j = 0; j < c; j++){
		int ma = 0;
		for(int k = 0; k < c; k++){
			if(j != k) ma = max(ma, ans[k]);
		}
		good[cycle[j]] = ma > ans[j];
	}
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
	n = n_;
	m = (int)u.size();
	g.resize(n);
	for(int i = 0; i < m; i++){
		edges.emplace_back(u[i], v[i]);
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}
	good.resize(m, -1);
	for(int i = 0; i < m; i++){
		if(good[i] == -1){
			calc(i);
		}
	}
	vector<int> r;
	for(int i = 0; i < m; i++) if(good[i] == 1) r.push_back(i);
	return r;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30