Submission #804287

#	Time	Username	Problem	Language	Result	Execution time	Memory
804287		ngrace	Simurgh (IOI17_simurgh)	C++14	30 / 100	3065 ms	3380 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));
	set<ii> dontbother;
	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> tree2;
				ve<int> treeInd(N);
				DSU inTree(N);
				int missing = cycle.size()-2;
				for(int c=0; c<cycle.size()-1; c++){
					int a=cycle[c], b=cycle[c+1];
					inTree.doUnion(a, b);
					tree2.push_back(edgeInd[a][b]);
					treeInd[c] = c;
					if(c==missing){
						treeInd[c] = -1;
						tree2.pop_back();
					}
				}
				for(auto it:baseTree){
					int a=it.fi.fi, b=it.fi.se;
					if(inTree.root(a)!=inTree.root(b)){
						tree2.push_back(it.se);
						inTree.doUnion(a,b);
					}
				}
				int ma=0;
				ve<int> cou(cycle.size()-1, -1);
				for(int c=0; c<cycle.size()-1; c++){
					int a=cycle[c], b=cycle[c+1];
					if(c!=missing){
						int newa=cycle[missing], newb=cycle[missing+1];
						tree2[treeInd[c]] = edgeInd[newa][newb];
						treeInd[missing] = treeInd[c];
						treeInd[c] = -1;
						missing = c;
					}
					cou[c] = count_common_roads(tree2);
					ma = max(ma, cou[c]);
				}

				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];
					if(dontbother.find({a,b}) != dontbother.end()) continue;
					int tmp = edgeInd[a][b];
					edgeInd[a][b] = edgeInd[b][a] = -1;
					if(findCutEdges()!=origCut){
						edgeInd[a][b] = edgeInd[b][a] = tmp;
						dontbother.insert({a,b});
					}
				}
			}
			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:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i=0; i < u.size(); i++){
      |               ~~^~~~~~~~~~
simurgh.cpp:136:19: 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:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:156:10: warning: unused variable 'a' [-Wunused-variable]
  156 |      int a=cycle[c], b=cycle[c+1];
      |          ^
simurgh.cpp:156:22: warning: unused variable 'b' [-Wunused-variable]
  156 |      int a=cycle[c], b=cycle[c+1];
      |                      ^
simurgh.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for(int c=0; c<cycle.size()-1; c++){
      |                  ~^~~~~~~~~~~~~~~
simurgh.cpp:175:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     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