oj.uz

Submission #804157

# Submission time Handle Problem Language Result Execution time Memory
804157 2023-08-03T07:25:07 Z ngrace Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 3932 KB 
#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

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.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB correct
2 Correct 1 ms 440 KB correct
3 Correct 1 ms 444 KB correct
4 Correct 1 ms 444 KB correct
5 Correct 1 ms 468 KB correct
6 Correct 1 ms 468 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 468 KB correct
9 Correct 1 ms 468 KB correct
10 Correct 1 ms 468 KB correct
11 Correct 1 ms 468 KB correct
12 Correct 1 ms 468 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 9 ms 568 KB correct
15 Correct 9 ms 568 KB correct
16 Correct 9 ms 444 KB correct
17 Correct 9 ms 468 KB correct
18 Correct 5 ms 468 KB correct
19 Correct 10 ms 468 KB correct
20 Correct 9 ms 568 KB correct
21 Correct 8 ms 468 KB correct
22 Correct 5 ms 468 KB correct
23 Correct 5 ms 548 KB correct
24 Correct 5 ms 468 KB correct
25 Correct 1 ms 468 KB correct
26 Correct 5 ms 552 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 6 ms 468 KB correct
31 Correct 5 ms 468 KB correct
32 Correct 5 ms 440 KB correct
33 Correct 6 ms 468 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB correct
2 Correct 1 ms 440 KB correct
3 Correct 1 ms 444 KB correct
4 Correct 1 ms 444 KB correct
5 Correct 1 ms 468 KB correct
6 Correct 1 ms 468 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 468 KB correct
9 Correct 1 ms 468 KB correct
10 Correct 1 ms 468 KB correct
11 Correct 1 ms 468 KB correct
12 Correct 1 ms 468 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 9 ms 568 KB correct
15 Correct 9 ms 568 KB correct
16 Correct 9 ms 444 KB correct
17 Correct 9 ms 468 KB correct
18 Correct 5 ms 468 KB correct
19 Correct 10 ms 468 KB correct
20 Correct 9 ms 568 KB correct
21 Correct 8 ms 468 KB correct
22 Correct 5 ms 468 KB correct
23 Correct 5 ms 548 KB correct
24 Correct 5 ms 468 KB correct
25 Correct 1 ms 468 KB correct
26 Correct 5 ms 552 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 6 ms 468 KB correct
31 Correct 5 ms 468 KB correct
32 Correct 5 ms 440 KB correct
33 Correct 6 ms 468 KB correct
34 Execution timed out 3057 ms 1212 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 212 KB correct
2 Correct 1 ms 468 KB correct
3 Runtime error 13 ms 3932 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB correct
2 Correct 1 ms 440 KB correct
3 Correct 1 ms 444 KB correct
4 Correct 1 ms 444 KB correct
5 Correct 1 ms 468 KB correct
6 Correct 1 ms 468 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 468 KB correct
9 Correct 1 ms 468 KB correct
10 Correct 1 ms 468 KB correct
11 Correct 1 ms 468 KB correct
12 Correct 1 ms 468 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 9 ms 568 KB correct
15 Correct 9 ms 568 KB correct
16 Correct 9 ms 444 KB correct
17 Correct 9 ms 468 KB correct
18 Correct 5 ms 468 KB correct
19 Correct 10 ms 468 KB correct
20 Correct 9 ms 568 KB correct
21 Correct 8 ms 468 KB correct
22 Correct 5 ms 468 KB correct
23 Correct 5 ms 548 KB correct
24 Correct 5 ms 468 KB correct
25 Correct 1 ms 468 KB correct
26 Correct 5 ms 552 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 6 ms 468 KB correct
31 Correct 5 ms 468 KB correct
32 Correct 5 ms 440 KB correct
33 Correct 6 ms 468 KB correct
34 Execution timed out 3057 ms 1212 KB Time limit exceeded
35 Halted 0 ms 0 KB -