#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];
}
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];
}
}
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);
return resp;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for(int i = 0; i < u.size(); i++) if(ans[i]==1)resp.pb(i);
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Incorrect |
164 ms |
5620 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
