| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137362 |
2019-07-27T13:58:03 Z |
wilwxk |
Simurgh (IOI17_simurgh) |
C++14 |
|
2 ms |
380 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=502;
int aresta[MAXN*MAXN][2];
vector<int> g[MAXN], gt[MAXN];
int rep[MAXN], tam[MAXN];
vector<int> config;
vector<int> respf;
bool usado[MAXN*MAXN], bom[MAXN];
int n, m;
bool debug=0;
int find(int cur) {
if(rep[cur]==cur) return cur;
return rep[cur]=find(rep[cur]);
}
void une(int a, int b) {
a=find(a); b=find(b);
if(a==b) return;
if(tam[a]<tam[b]) swap(a, b);
rep[a]=b;
}
void geradora() {
srand(time(0)+n+m);
for(int i=0; i<n; i++) rep[i]=i, tam[i]=i;
for(int i=0; i<m; i++) {
int a=aresta[i][0]; int b=aresta[i][1];
if(find(a)==find(b)) continue;
gt[a].push_back(i);
gt[b].push_back(i);
une(a, b);
if(debug) printf("tree:: %d %d // %d\n", a, b, i);
}
}
int query() {
if(debug){for(auto cur : config) printf("%d ", cur); cout << ">> " << count_common_roads(config) << endl;}
for(int i=0; i<n; i++) rep[i]=i;
for(auto cur : config) une(aresta[cur][0], aresta[cur][1]);
for(int i=0; i<n; i++) if(find(i)!=find(0)) return MAXN;
return count_common_roads(config);
}
void solve(int cur, int pid) {
random_shuffle(g[cur].begin(), g[cur].end());
int ori=query();
vector<int> aux; aux=config; config.clear();
for(auto cur : aux) if(cur!=pid) config.push_back(cur);
config.push_back(pid);
if(g[cur].size()==1) {
respf.push_back(pid);
bom[pid]=1;
return;
}
for(auto vid : g[cur]) {
if(vid==pid||bom[vid]||usado[vid]) continue;
config.pop_back();
config.push_back(vid);
int val=query();
config.pop_back();
config.push_back(pid);
if(val!=ori) {
if(val<ori) respf.push_back(pid), bom[pid]=1;
else respf.push_back(vid), bom[vid]=1;
break;
}
}
if(debug) printf("solved %d\n", respf.back());
}
void predfs(int cur, int pid) {
if(pid!=-1) config.push_back(pid), usado[pid]=1 ;
for(auto vid : gt[cur]) {
if(vid==pid) continue;
int viz= aresta[vid][aresta[vid][0]==cur];
predfs(viz, vid);
}
if(pid==-1) return;
}
void dfs(int cur, int pid) {
if(debug) printf("dfs %d %d\n", cur, pid);
for(auto vid : gt[cur]) {
if(vid==pid) continue;
int viz= aresta[vid][aresta[vid][0]==cur];
dfs(viz, vid);
}
if(pid==-1) return;
solve(cur, pid);
}
std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
n=N; m=U.size();
for(int i=0; i<m; i++) {
int a=U[i]; int b=V[i];
aresta[i][0]=a; aresta[i][1]=b;
g[a].push_back(i);
g[b].push_back(i);
}
geradora();
predfs(0, -1);
dfs(0, -1);
if(debug) for(auto cur : respf) printf("%d ", cur);
return respf;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
