oj.uz

Submission #804287

# Submission time Handle Problem Language Result Execution time Memory
804287 2023-08-03T07:48:29 Z ngrace Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 3380 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));
	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

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

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB correct
2 Correct 1 ms 468 KB correct
3 Correct 1 ms 468 KB correct
4 Correct 1 ms 468 KB correct
5 Correct 1 ms 468 KB correct
6 Correct 1 ms 468 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 468 KB correct
9 Correct 0 ms 468 KB correct
10 Correct 1 ms 468 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 468 KB correct
13 Correct 0 ms 468 KB correct
14 Correct 8 ms 568 KB correct
15 Correct 8 ms 564 KB correct
16 Correct 8 ms 468 KB correct
17 Correct 7 ms 468 KB correct
18 Correct 3 ms 468 KB correct
19 Correct 7 ms 568 KB correct
20 Correct 7 ms 468 KB correct
21 Correct 8 ms 560 KB correct
22 Correct 4 ms 468 KB correct
23 Correct 4 ms 552 KB correct
24 Correct 3 ms 468 KB correct
25 Correct 1 ms 468 KB correct
26 Correct 4 ms 468 KB correct
27 Correct 4 ms 480 KB correct
28 Correct 2 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 4 ms 468 KB correct
31 Correct 4 ms 468 KB correct
32 Correct 4 ms 468 KB correct
33 Correct 4 ms 468 KB correct
34 Execution timed out 3065 ms 1060 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 14 ms 3380 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 0 ms 468 KB correct
2 Correct 1 ms 468 KB correct
3 Correct 1 ms 468 KB correct
4 Correct 1 ms 468 KB correct
5 Correct 1 ms 468 KB correct
6 Correct 1 ms 468 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 468 KB correct
9 Correct 0 ms 468 KB correct
10 Correct 1 ms 468 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 468 KB correct
13 Correct 0 ms 468 KB correct
14 Correct 8 ms 568 KB correct
15 Correct 8 ms 564 KB correct
16 Correct 8 ms 468 KB correct
17 Correct 7 ms 468 KB correct
18 Correct 3 ms 468 KB correct
19 Correct 7 ms 568 KB correct
20 Correct 7 ms 468 KB correct
21 Correct 8 ms 560 KB correct
22 Correct 4 ms 468 KB correct
23 Correct 4 ms 552 KB correct
24 Correct 3 ms 468 KB correct
25 Correct 1 ms 468 KB correct
26 Correct 4 ms 468 KB correct
27 Correct 4 ms 480 KB correct
28 Correct 2 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 4 ms 468 KB correct
31 Correct 4 ms 468 KB correct
32 Correct 4 ms 468 KB correct
33 Correct 4 ms 468 KB correct
34 Execution timed out 3065 ms 1060 KB Time limit exceeded
35 Halted 0 ms 0 KB -