Submission #804157

#	Time	Username	Problem	Language	Result	Execution time	Memory
804157		ngrace	Simurgh (IOI17_simurgh)	C++14	30 / 100	3057 ms	3932 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;
#define ve vector
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second

int N;
set<int> ans;
int edgeInd[240][240];

struct DSU{
	int par[500];
	int si=0;
	DSU(int siz){
		si=siz;
		reset();
	}
	void reset(){
		for(int i=0; i<si; i++) par[i]=i;
	}
	int root(int x) {
		return (x==par[x]) ? x : par[x]=root(par[x]);
	}
	void doUnion(int a, int b){
		par[root(a)]=root(b);
	}
};

ve<pair<ii, int>> baseTree;
bool treeVis[500];
void treeDFS(int x){
	treeVis[x]=true;
	for(int i=0; i<N; i++){
		if(edgeInd[x][i]==-1) continue;
		if(!treeVis[i]){
			baseTree.push_back({{x, i}, edgeInd[x][i]});
			treeDFS(i);
		}
	}
}

ve<int> cycleVis(240, 0);
ve<int> cycle;
int cycleIter=0;
int cycleStart;
bool cycleDFS(int x, int par){
	if(x==cycleStart){
		cycle.push_back(x);
		return true;
	}
	if(cycleVis[x]==cycleIter) return false;
	cycleVis[x] = cycleIter;
	cycle.push_back(x);
	for(int i=0; i<N; i++){
		if(edgeInd[x][i]==-1 || i==par) continue;
		if(cycleDFS(i, x)) return true;
	}
	cycle.pop_back();
	return false;
}
bool findCycle(int a, int b){
	cycleIter++;
	cycle = {a};
	cycleVis[a] = cycleIter;
	cycleStart = a;
	return cycleDFS(b, a);
}

int cutTime=0;
int cutIter=0;
ve<int> cutVis(240, false);
ve<int> firstTime(240, -1);
ve<int> lowTime(240, -1);
int numCut=0;
void cutDFS(int cur, int par){
	cutVis[cur]=cutIter;
	firstTime[cur] = lowTime[cur] = cutTime++;
	for(int i=0; i<N; i++){
		if(edgeInd[cur][i]==-1 || i==par) continue;

		if(cutVis[i]==cutIter) lowTime[cur] = min(lowTime[cur], firstTime[i]);
		else{
			cutDFS(i, cur);
			lowTime[cur] = min(lowTime[cur], lowTime[i]);
			if(lowTime[i] > firstTime[cur]) {
				numCut++;
			}
		}
	}
}
int findCutEdges(){
	cutIter++;
	cutTime=0;
	numCut=0;
	cutDFS(0, 0);
	return numCut;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;

	if(n==2){
		ve<int> res = {0};
		return res;
	}

	for(int i=0; i<240; i++){
		for(int j=0; j<240; j++){
			edgeInd[i][j] = -1;
		}
	}
	for(int i=0; i < u.size(); i++){
		edgeInd[u[i]][v[i]] = i;
		edgeInd[v[i]][u[i]] = i;
	}

	treeDFS(0);

	int origCut = findCutEdges();

	ve<ve<bool>> known(N, ve<bool>(N, false));
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(edgeInd[i][j]==-1 || known[i][j]) continue;
			if(findCycle(i, j)){
				ve<int> cou(cycle.size()-1, -1);
				int ma=0;
				for(int miss=0; miss<cycle.size()-1; miss++){
					DSU con(N);
					ve<int> tree;
					//can speed this up using the missing thingy
					for(int c=0; c<cycle.size()-1; c++){
						if(miss==c) continue;
						int a=cycle[c], b=cycle[c+1];
						tree.push_back(edgeInd[a][b]);
						con.doUnion(a, b);
					}
					for(auto it:baseTree){
						if(con.root(it.fi.fi) != con.root(it.fi.se)){
							tree.push_back(it.se);
							con.doUnion(it.fi.fi, it.fi.se);
						}
					}
					cou[miss] = count_common_roads(tree);
					ma=max(cou[miss], ma);
				}
				for(int c=0; c<cycle.size()-1; c++){
					int a=cycle[c], b=cycle[c+1];
					known[a][b] = known[b][a] = true;
					if(cou[c]<ma && ans.find(edgeInd[a][b]) == ans.end()){
						ans.insert(edgeInd[a][b]);
					}
				}
				for(int c=0; c<cycle.size()-1; c++){
					int a=cycle[c], b=cycle[c+1];
					int tmp = edgeInd[a][b];
					edgeInd[a][b] = edgeInd[b][a] = -1;
					if(findCutEdges()!=origCut) edgeInd[a][b] = edgeInd[b][a] = tmp;
				}
			}
			else{
				ans.insert(edgeInd[i][j]);
				known[i][j] = known[j][i] = true;
			}
		}
	}

	ve<int> res;
	for(int i:ans) res.push_back(i);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i=0; i < u.size(); i++){
      |               ~~^~~~~~~~~~
simurgh.cpp:132:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int miss=0; miss<cycle.size()-1; miss++){
      |                     ~~~~^~~~~~~~~~~~~~~
simurgh.cpp:136:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |      for(int c=0; c<cycle.size()-1; c++){
      |                   ~^~~~~~~~~~~~~~~
simurgh.cpp:151:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:158:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~

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