oj.uz

Submission #1011795

# Submission time Handle Problem Language Result Execution time Memory
1011795 2024-07-01T08:42:52 Z jcelin Simurgh (IOI17_simurgh) C++14
0 / 100
 77 ms 3132 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end() 

const int MAXN = 1e6 + 7;


struct uf{
	int par[MAXN], sz[MAXN];
	
	void res(int n){
		for(int i=0; i<n; i++) par[i] = i, sz[i] = 1;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	bool unite(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
		return 1;
	}
}s;



/*
int count_common_roads(vi r){
	
}
*/

vi find_roads(int n, vi u, vi v){
	vi ans;
	int m = u.size();
	ans.clear();
	for(int i=0; i<n; i++){
		if((int)ans.size() + 1 == n) break;	
		vi x, y;
		for(int j=0; j<m; j++){
			if(u[j] == i or v[j] == i) x.PB(j);
			else y.PB(j);
		}
		
		if(x.size() == 1){
			ans.PB(x[0]);
			continue;
		}
		
		s.res(n);
		vi toq;
		for(auto &t : y) if(s.unite(u[t], v[t])) toq.PB(t);
		
		
		vii ret;
		for(auto &t : x){
			toq.PB(t);
			int vl = count_common_roads(toq);
			toq.PPB();
			ret.PB({vl, t});
		}
		sort(all(ret));
		int vl = ret.back().X;
		for(auto &t : ret) if(t.X == vl) ans.PB(t.Y);
		
		sort(all(ans));
		ans.erase(unique(all(ans)), ans.end());
	}
	return ans;
}

/*
void solve(){
	int n, m;
	cin >> n >> m;
	vi x, y;
	for(int i=1; i<=m; i++){
		int a, b;
		cin >> a >> b;
		x.PB(a);
		y.PB(b);
	}
	find_roads(n, m, x, y);
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 77 ms 3132 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -