oj.uz

Submission #982859

# Submission time Handle Problem Language Result Execution time Memory
982859 2024-05-14T20:29:38 Z Lalic Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 348 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int pai[505], peso[505], mark[505];
vector<pii> adj[505];

int find(int x){ return (pai[x]==x ? x : pai[x]=find(pai[x])); }
void join(int a, int b){
	a=find(a); b=find(b);
	if(a==b) return;
	
	if(peso[a]>peso[b]) swap(a, b);
	pai[a]=b;
	peso[b]=max(peso[b], peso[a]+1);
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m=(int)u.size();
	
	vector<pii> aresta;
	
	for(int i=0;i<m;i++){
		aresta.pb({u[i], v[i]});
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	
	vector<int> sk(m);
	for(int i=1;i<n;i++){
		if(mark[i]) continue;
		
		for(int j=0;j<n;j++) pai[j]=j, peso[j]=0;
		
		vector<int> curr;
		
		for(int j=0;j<m;j++){
			if(sk[j]){
				join(aresta[j].fi, aresta[j].se);
				curr.pb(j);
			}
		}
		
		for(int j=0;j<m;j++){
			pii at=aresta[j];

			if(at.fi==i || at.se==i) continue;
			
			if(find(at.fi)!=find(at.se)){
				join(at.fi, at.se);
				curr.pb(j);
			}
		}
		
		for(auto at : adj[i]){
			if(find(0)==find(at.fi)) continue;
			join(i, at.fi);
			curr.pb(at.se);
		}
		
		vector<int> lh={adj[i][0].se}, rh;
		
		curr.pb(adj[i][0].se);
		int ini=count_common_roads(curr);
		curr.pop_back();
		
		bool useRH=0;
		
		for(int j=1;j<(int)adj[i].size();j++){
			curr.pb(adj[i][j].se);
			
			int qnt=count_common_roads(curr);
			
			curr.pop_back();
			
			if(qnt!=ini){
				if(qnt>ini) useRH=1;
				rh.pb(adj[i][j].se);
			}
			else lh.pb(adj[i][j].se);
		}
		
		if(!useRH){
			for(auto at : lh){
				//royal.pb(aresta[at]);
				sk[at]=1;
				mark[aresta[at].fi]=1;
				mark[aresta[at].se]=1;
			}
		}
		else{
			for(auto at : rh){
				//royal.pb(aresta[at]);
				sk[at]=1;
				mark[aresta[at].fi]=1;
				mark[aresta[at].se]=1;
			}
		}
	}
	
	vector<int> ans;
	for(int i=0;i<m;i++)
		if(sk[i]) ans.pb(i);
		
	return ans;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -