| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 172311 |
2020-01-01T06:45:53 Z |
qkxwsm |
Simurgh (IOI17_simurgh) |
C++14 |
|
3 ms |
504 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "simurgh.h"
using namespace std;
using namespace __gnu_pbds;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
struct custom_hash
{
template<class T>
T operator()(T a) const
{
return (a ^ (a >> 15)) ^ (a * 69);
}
};
template<class T, class U>
using hash_table = gp_hash_table<T, U, custom_hash>;
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define MAXN 513
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, T;
int eid[MAXN][MAXN];
int st[MAXN], ft[MAXN];
hash_table<int, int> rec[MAXN];
vi edge[MAXN];
bitset<MAXN> seen;
int parent[MAXN], depth[MAXN];
int ans[MAXN * MAXN];
vi quer;
vi ret;
int get(int a, int b)
{
if (rec[a].find(b) != rec[a].end()) return rec[a][b];
quer.clear();
if (a == 0 && b == 0)
{
FOR(i, 1, N)
{
quer.PB(eid[i][parent[i]]);
}
rec[a][b] = count_common_roads(quer);
}
else
{
FOR(i, 1, N)
{
if (i == a) continue;
quer.PB(eid[i][parent[i]]);
}
quer.PB(b);
rec[a][b] = count_common_roads(quer);
}
return rec[a][b];
//take the tree, except delete a and add edge b.
}
void dfs(int u, int p)
{
st[u] = T; ft[u] = T;
T++;
seen[u] = true;
for (int v : edge[u])
{
if (v == p) continue;
if (seen[v])
{
ckmin(ft[u], st[v]);
continue;
}
parent[v] = u;
depth[v] = depth[u] + 1;
dfs(v, u);
ckmin(ft[u], ft[v]);
}
}
vi find_roads(int n, vi e1, vi e2)
{
N = n; M = SZ(e1);
FOR(i, 0, M)
{
edge[e1[i]].PB(e2[i]);
edge[e2[i]].PB(e1[i]);
eid[e1[i]][e2[i]] = i;
eid[e2[i]][e1[i]] = i;
ans[i] = -1;
}
if (N >= 3 && M == N * (N - 1) / 2)
{
FOR(i, 0, M) ans[i] = 0;
int R = -1;
FOR(i, 0, N)
{
quer.clear();
FOR(j, 0, N)
{
if (i == j) continue;
quer.PB(eid[i][j]);
}
depth[i] = count_common_roads(quer);
// cerr << depth[i] << ' ';
}
// cerr << endl;
FOR(i, 0, N)
{
if (depth[i] == 1)
{
R = i;
break;
}
}
//R is a leaf.
//for each of the N edges connected to R, check to see if it's the on one.
FOR(i, 0, N)
{
if (i == R) continue;
quer.clear();
int s = 0;
while(s == R || s == i) s++;
FOR(j, 0, N)
{
if (j == s || j == R || j == i) continue;
quer.PB(eid[s][j]);
}
quer.PB(eid[R][s]);
quer.PB(eid[R][i]);
// cerr << "sz " << SZ(quer) << endl;
int si = count_common_roads(quer);
quer.pop_back();
quer.PB(eid[s][i]);
int ri = count_common_roads(quer);
quer.pop_back();
quer.pop_back();
quer.PB(eid[s][i]);
quer.PB(eid[R][i]);
int rs = count_common_roads(quer);
if (ri < rs || ri < si)
{
T = i;
break;
}
//is R...i on?
}
ans[eid[R][T]] = 1;
FOR(i, 0, N)
{
if (i == R) continue;
int lo = -1, hi;
vi idk;
FOR(j, 0, N)
{
if (i == j || j == R) continue;
idk.PB(j);
}
FOR(j, 0, depth[i])
{
lo++; hi = SZ(idk) - 1;
while(hi > lo)
{
int mid = (hi + lo) >> 1;
quer.clear();
FOR(k, 0, mid + 1)
{
quer.PB(eid[idk[k]][i]);
}
FOR(k, mid + 1, SZ(idk))
{
quer.PB(eid[idk[k]][R]);
}
quer.PB(eid[R][i]);
int x = count_common_roads(quer);
FOR(k, mid + 1, SZ(idk))
{
if (idk[k] == T) x--;
}
if (i == T) x--;
if (x >= j + 1) hi = mid;
else lo = mid + 1;
}
ans[eid[i][idk[lo]]] = 1;
}
}
}
else
{
parent[0] = N; parent[N] = N;
dfs(0, N);
// FOR(i, 1, N)
// {
// cerr << i << " -> " << parent[i] << endl;
// }
//1 = yes, -1 = no, 0 = idk
FOR(ed, 0, M)
{
int u = e1[ed], v = e2[ed];
if (depth[u] > depth[v]) swap(u, v);
if (u == parent[v]) continue;
//lol there are no side edges.
vi nodes; nodes.PB(v);
while(nodes.back() != u)
{
nodes.PB(parent[nodes.back()]);
}
assert(nodes.back() == u);
//you know the answer?
int s = -1;
FOR(i, 0, SZ(nodes) - 1)
{
if (ans[eid[nodes[i]][nodes[i + 1]]] != -1)
{
s = nodes[i];
break;
}
}
if (s == -1)
{
int mn = get(0, 0), mx = mn;
FOR(i, 0, SZ(nodes) - 1)
{
int x = get(nodes[i], ed);
ckmin(mn, x);
ckmax(mx, x);
}
FOR(i, 0, SZ(nodes) - 1)
{
int x = get(nodes[i], ed);
ans[eid[nodes[i]][nodes[i + 1]]] = ((mn == mx || x == mx) ? 0 : 1);
}
int x = get(0, 0);
ans[ed] = ((mn == mx || x == mx) ? 0 : 1);
}
else
{
int x = get(s, ed);
int y = get(0, 0);
//y + ed - s = x -> ed = x + s - y
ans[ed] = x + ans[eid[s][parent[s]]] - y;
FOR(i, 0, SZ(nodes) - 1)
{
int ed1 = eid[nodes[i]][nodes[i + 1]];
if (ans[ed1] != -1) continue;
x = get(nodes[i], ed);
//x = y + ed - ed1
ans[ed1] = y - x + ans[ed];
}
}
}
FOR(u, 1, N)
{
if (ans[eid[u][parent[u]]] == -1)
{
ans[eid[u][parent[u]]] = 1;
}
}
}
FOR(i, 0, M)
{
assert(ans[i] == 0 || ans[i] == 1);
if (ans[i] == 1) ret.PB(i);
}
// cerr << "RETURNS:";
// for (int x : ret)
// {
// cerr << ' ' << x;
// }
// cerr << endl;
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
correct |
| 2 |
Correct |
2 ms |
504 KB |
correct |
| 3 |
Incorrect |
2 ms |
504 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
correct |
| 2 |
Correct |
2 ms |
504 KB |
correct |
| 3 |
Incorrect |
2 ms |
504 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
correct |
| 2 |
Correct |
2 ms |
504 KB |
correct |
| 3 |
Incorrect |
2 ms |
504 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Incorrect |
2 ms |
504 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
correct |
| 2 |
Correct |
2 ms |
504 KB |
correct |
| 3 |
Incorrect |
2 ms |
504 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
