| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283960 |
2020-08-26T10:05:45 Z |
balbit |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
512 KB |
#include <bits/stdc++.h>
#ifndef BALBIT
#include "simurgh.h"
#endif
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template <typename T> void _do(T && x) {cerr<<x<<endl;}
template <typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif
const int maxn = 503;
#ifdef BALBIT
int count_common_roads(vector<int> x){
for (int y : x) cout<<y<<" ";
cout<<endl;
int r; cin>>r; return r;
}
#endif
vector<pii> g[maxn];
int par[maxn];
int find(int x){return x==par[x]?x:par[x]=find(par[x]);}
bool fun[maxn];
vector<int> spn(vector<int> a){
memset(fun, 0, sizeof fun);
for (int x : a) par[x] = x, fun[x] = 1;
vector<int>re;
for (int x : a) {
for (pii u : g[x]) {
if (fun[u.f] && find(u.f)!=find(x)) {
par[find(u.f)]=find(x);
re.pb(u.s);
}
}
}
// assert(SZ(re) == SZ(a)-1);
return re;
}
bool done[maxn];
bool seen[maxn];
int color[maxn];
bool poker[maxn];
int n;
// vector<int> hre;
void dfs(int v, int c) {
seen[v] = 1; color[v] = c;
// vv.pb(v);
for (pii u : g[v]) {
if (!seen[u.f]) dfs(u.f, c);
}
}
int m;
bool baba[100000];
vector<int> ret;
void go(int v, int p) {
bug("DFS", v);
done[v] = 1;
for (int i = 0; i<maxn; ++i) seen[i] = done[i];
seen[v] = 1;
memset(color, 0, sizeof color);
int NOW = 1;
for (pii pp : g[v]) {
int u = pp.f;
if (!seen[u]) {
bug(v,u);
dfs(u, NOW);
vector<int> t1, t2;
for (int i = 0; i<n; ++i) {
(color[i] == NOW? t1 : t2).pb(i);
}
t1 = spn(t1); t2 = spn(t2);
for (int x : t2) t1.pb(x);
vector<int> rl;
int haspoke = -1;
for (pii XX : g[v]) {
int ty = XX.f;
if (color[ty] == NOW) {
if (poker [ty]) {
// guarantee bad
vector<int> tmp = t1; tmp.pb(XX.s);
haspoke = count_common_roads(tmp);
}else{
vector<int> tmp = t1; tmp.pb(XX.s);
rl.pb(count_common_roads(tmp));
}
}
}
int IT = 0;
int bar = *max_element(ALL(rl));
for (pii XX : g[v]) {
int ty = XX.f;
if (color[ty]== NOW) {
if (rl[IT] == bar && rl[IT] != haspoke) {
if (!baba[XX.s]) ret.pb(XX.s);
// bug(XX.s,"Impo");
baba[XX.s] = 1;
poker[XX.f] = 1;
// done[XX.s] = 1;
}
++IT;
}
}
++NOW;
}
}
// done[v] = 0;
for (pii pp : g[v]) {
if (!done[pp.f] && baba[pp.s] && pp.f != p) go(pp.f, v);
}
}
vector<int> find_roads(int NN, vector<int> UU, vector<int> VV) {
n = NN;
m = SZ(UU);
vector<int> re;
for (int i = 0; i<m; ++i) {
g[UU[i]].pb({VV[i], i});
g[VV[i]].pb({UU[i], i});
}
go(0,-1);
return ret;
}
#ifdef BALBIT
signed main(){
IOS();
vector<int> hmm = find_roads(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 3});
for (int x : hmm) bug(x);
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
correct |
| 2 |
Incorrect |
0 ms |
384 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
