oj.uz

Submission #400203

# Submission time Handle Problem Language Result Execution time Memory
400203 2021-05-07T15:13:47 Z MatheusLealV Simurgh (IOI17_simurgh) C++17
19 / 100
 717 ms 8164 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define N 520
using namespace std;
typedef pair<int, int> pii;

pii ed[N*N];
vector<pii> grafo[N];
vector<int> tree, T[N];
int cnt, grau[N], id[N][N], ans[N*N];;
int vis[N], n, x[N], filhos[N], pai[N], nivel[N], dfsnum[N], dfslow[N];
struct dsu{
    int pai[N], peso[N];
    int Find(int x){
        if(x==pai[x]) return x;
        return pai[x] = Find(pai[x]);
    }
    int join(int a, int b){
        a = Find(a), b = Find(b);
        if(a== b) return 0;
        if(peso[a] > peso[b]) swap(a, b);
        pai[a]=b;
        if(peso[a]==peso[b])peso[b]++;
        return 1;
    }
    void init(){
        for(int i = 0; i <= n; i++){
            pai[i]=i;
            peso[i]=0;
        }
    }
} UF;
void dfs(int x){
	dfsnum[x] = dfslow[x] = ++cnt;
	vis[x] = 1;
	for(auto v: grafo[x]){
		if(!vis[v.f]){
			tree.pb(v.s);
			pai[v.f] = x;
			nivel[v.f] = nivel[x] + 1;
			T[x].pb(v.f);
			T[v.f].pb(x);
			dfs(v.f);
			if(dfslow[v.f] > dfsnum[x]) ans[v.s] = 1;
			dfslow[x]=min(dfslow[v.f], dfslow[x]);
		}
		else if(v.f != pai[x]) dfslow[x] = min(dfsnum[v.f], dfslow[x]);
	}
}
vector<int> find_roads(int NN, vector<int> u, vector<int> v) {
	// assert(u.size() == NN*(NN-1)/2);
	if(NN == 2){
		vector<int> ans;
		for(int i = 0; i < sz(u); i++) ans.pb(i);
		return ans;
	}
	n = NN;
	for(int i = 0; i < sz(u); i++){
		++u[i];++v[i];
		grafo[u[i]].pb({v[i], i});
		grafo[v[i]].pb({u[i], i});
		ed[i] = {u[i], v[i]};
		id[u[i]][v[i]] = id[v[i]][u[i]] = i;
	}

	dfs(1);
	sort(all(tree));
	int A = count_common_roads(tree);
	for(int x = 1; x <= n; x++){
		for(auto v: grafo[x]){
			if(binary_search(all(tree), v.s) or v.f > x) continue;
			int a = x, b = v.f;
			if(nivel[a] < nivel[b]) swap(a, b);
			vector<int> caras;
			while(a != b){
				caras.pb(id[a][pai[a]]);
				a = pai[a];
			}
			int good = -1,tot=0;
			for(auto w: caras)
				if(ans[w] != 0) good = w,tot++;
			if(tot == sz(caras)) continue;
			if(good == -1){
				vector<int> iguais;
				for(auto w: caras){
					vector<int> atual;
					atual.pb(v.s);
					for(auto t: tree){
						if(t == w) continue;
						atual.pb(t);
					}
					int X = count_common_roads(atual);
					if(X == A) iguais.pb(w); // w = v.s
					else if(X < A){
						ans[w] = 1;
						ans[v.s] = -1;
					}
					else{
						ans[w] = -1;
						ans[v.s] = 1;
					}
				}
				if(ans[v.s] == 0) ans[v.s]=-1;
				for(auto y: iguais) ans[y] = ans[v.s];
			}
			else{
				vector<int> atual;
				atual.pb(v.s);
				for(auto t :tree){
					if(t==good) continue;
					atual.pb(t);
				}
				// T - Xgood + Xv
				int X = count_common_roads(atual); // tira good e coloca v.s
				if(X == A) ans[v.s] = ans[good];
				else if(X > A) ans[v.s] = 1;
				else ans[v.s] = -1;
				for(auto w: caras){
					if(ans[w] != 0) continue;
					vector<int> atual;
					atual.pb(v.s);
					for(auto t: tree){
						if(t == w) continue;
						atual.pb(t);
					}
					int Y = count_common_roads(atual); // T - Xw + Xv
					if(Y == X) ans[w] = ans[good];
					else if(Y > X) ans[w] = -1;
					else ans[w] = 1;
				}
			}
		}
	}

	for(int i = 1; i <= n; i++){
		vector<int> ed;
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			ed.pb(id[i][j]);
		}
		grau[i] = count_common_roads(ed);
	}
	vector<int> block(n+1);
	while(true){
		int achou = 0;
		for(int i = 1; i <= n; i++){
			if(block[i] or grau[i] - filhos[i] != 1) continue;
			achou=1;
			vector<int> caras;
			block[i] = 1;
			for(auto v: grafo[i]){
				if(block[v.f]) continue;
				caras.pb(v.f);
			}
			int ini = 0, fim = sz(caras), mid, best=-1;
			while(fim >= ini){
				mid = (ini+fim)/2;
				UF.init();
				vector<pii> arestas;
				for(auto e: tree) arestas.pb({1, e});
				for(int j = 0; j < mid; j++){
					arestas.pb({0, id[i][caras[j]]});
				}
				sort(all(arestas));
				vector<int> curr;
				int aux=0;
				set<int> usados;
				for(int t = 0; t < sz(arestas); t++){
					int a = ed[arestas[t].s].f, b = ed[arestas[t].s].s;
					if(UF.join(a, b)){
						curr.pb(arestas[t].s);
						usados.insert(arestas[t].s);
					}
					else if(arestas[t].f == 1 ){
						aux += max(0,ans[arestas[t].s]);
					}
				}
				int C = count_common_roads(curr);
				if(C - (A-aux) >= 1){
					best = id[i][caras[mid-1]];
					fim = mid - 1;
				}
				else ini = mid + 1;
			}
			int pai = ed[best].f;
			if(pai==i)pai=ed[best].s;
			filhos[pai]++;
			ans[best] = 1;
		}

		if(!achou) break;
	}

	vector<int> resp;
	for(int i = 0; i < u.size(); i++) if(ans[i]==1)resp.pb(i);
	//cout<<"MY\n";
	//for(auto e: resp) cout<<"resp | "<<e<<" | "<<u[e]<<" "<<v[e]<<"\n";
	return resp;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:202:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |  for(int i = 0; i < u.size(); i++) if(ans[i]==1)resp.pb(i);
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 415 ms 5200 KB correct
4 Correct 698 ms 8032 KB correct
5 Correct 700 ms 8044 KB correct
6 Correct 704 ms 8004 KB correct
7 Correct 717 ms 8132 KB correct
8 Correct 713 ms 8024 KB correct
9 Correct 697 ms 8088 KB correct
10 Correct 703 ms 8004 KB correct
11 Correct 710 ms 8164 KB correct
12 Correct 715 ms 8020 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 690 ms 8048 KB correct
15 Correct 698 ms 8044 KB correct

Subtask #5
0 / 30.0

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