| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 152654 |
2019-09-09T00:22:48 Z |
qkxwsm |
Simurgh (IOI17_simurgh) |
C++14 |
|
248 ms |
6376 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#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 SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 513
#define INF 1000000007
#define MOD 1000000931
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, Q, M, T, K;
int eid[MAXN][MAXN];
int res[MAXN][MAXN];
ll pw[MAXN * MAXN], PW[MAXN * MAXN];
vi edge[MAXN];
vi edge1[MAXN];
int parent[MAXN];
bitset<MAXN> seen;
map<ll, int> mp;
vi ans;
struct dsu
{
int dsu[MAXN];
void init()
{
FOR(i, 0, N) dsu[i] = i;
}
int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
bool merge(int u, int v)
{
u = get(u); v = get(v);
if (u == v) return false;
dsu[v] = u; return true;
}
};
void dfs1(int u, int p)
{
for (int v : edge1[u])
{
if (v == p) continue;
parent[v] = u;
dfs1(v, u);
}
}
vi getpath(int u, int v)
{
vi pu, pv;
while(u != 0)
{
pu.PB(u);
u = parent[u];
}
pu.PB(0);
while(v != 0)
{
pv.PB(v);
v = parent[v];
}
pv.PB(0);
int r = -1;
while(!pu.empty() && !pv.empty() && pu.back() == pv.back())
{
r = pu.back();
pu.pop_back(); pv.pop_back();
}
pu.PB(r);
pu.insert(pu.end(), ALL(pv));
return pu; //gets the path from pu to pv in O(N) time.
}
dsu D;
int ask(vi x)
{
// cerr << "ASK\n";
// for (int a : x)
// {
// cerr << a << ' ';
// }
// cerr << endl;
ll sum = 0, SUM = 0;
for (int y : x)
{
sum += pw[y]; if (sum >= INF) sum -= INF;
SUM += PW[y]; if (SUM >= MOD) SUM -= MOD;
}
ll key = sum * MOD + SUM;
auto it = mp.find(key);
if (it != mp.end()) return it -> se;
int res = count_common_roads(x);
mp[key] = res;
// cerr << "RECEIVE " << res << endl;
return res;
}
vi find_roads(int n, vi U, vi V)
{
N = n; M = SZ(U);
pw[0] = 1; PW[0] = 1;
FOR(i, 0, M)
{
if (U[i] > V[i]) swap(U[i], V[i]);
edge[U[i]].PB(V[i]);
edge[V[i]].PB(U[i]);
eid[U[i]][V[i]] = i;
eid[V[i]][U[i]] = i;
res[U[i]][V[i]] = -1;
res[V[i]][U[i]] = -1;
pw[i + 1] = pw[i] + pw[i]; if (pw[i + 1] >= INF) pw[i + 1] -= INF;
PW[i + 1] = PW[i] + PW[i]; if (PW[i + 1] >= MOD) PW[i + 1] -= MOD;
}
D.init();
// cerr << "SPANNING TREE\n";
FOR(u, 0, N)
{
for (int v : edge[u])
{
if (v < u) continue;
if (D.merge(u, v))
{
// cerr << u << ' ' << v << endl;
edge1[u].PB(v);
edge1[v].PB(u);
}
}
}
dfs1(0, N);
parent[0] = N;
// cerr << "SOLVE\n";
//ok now the idea is: for all edges, find a cycle.
//if the cycle has all new edges, you solve the cycle in O(size)
//else, you can just solve the edge using the known edge.
FOR(u, 0, N)
{
for (int v : edge[u])
{
if (v < u) continue;
if (res[u][v] != -1) continue;
if (u == parent[v] || v == parent[u]) continue;
// cerr << "NEW ROUND\n";
//ok solve u, v.
//find any cycle that (u, v) is part of.
vi cyc = getpath(u, v); cyc.PB(u);
// cerr << "getpath " << u << ' ' << v << endl;
// for (int x : cyc)
// {
// cerr << x << ' ';
// }
// cerr << endl;
vi qry; int mn = 0;
FOR(i, 0, SZ(cyc) - 1)
{
qry.PB(eid[cyc[i]][cyc[i + 1]]);
}
int solved = -1;
FOR(i, 0, SZ(cyc) - 2)
{
int w = cyc[i], x = cyc[i + 1];
if (res[w][x] != -1)
{
// cerr << "SOLVED " << w << ' ' << x << endl;
// w..x is solved.
solved = i;
break;
}
}
//complete the tree
seen.reset();
FOR(i, 0, SZ(cyc) - 2)
{
int w = cyc[i], x = cyc[i + 1];
if (x == parent[w]) seen[w] = true;
else seen[x] = true;
}
FOR(i, 1, N)
{
if (!seen[i])
{
// cerr << "NOTVIS " << i << endl;
qry.PB(eid[i][parent[i]]);
}
}
// cerr << "QRY\n";
// for (int x : qry)
// {
// cerr << x << ' ';
// }
// cerr << endl;
if (solved == -1)
{
vi dp(SZ(cyc) - 1);
assert(SZ(qry) == N);
FOR(i, 0, SZ(cyc) - 1)
{
int x = qry[i];
swap(qry[i], qry[N - 1]);
qry.pop_back();
dp[i] = ask(qry);
ckmax(mn, dp[i]);
qry.PB(x);
swap(qry[i], qry[N - 1]);
}
// cerr << "mn = " << mn << endl;
FOR(i, 0, SZ(cyc) - 1)
{
int w = cyc[i], x = cyc[i + 1];
res[w][x] = (dp[i] == mn ? 0 : 1);
// cerr << w << ' ' << x << ' ' << dp[i] << ' ' << res[w][x] << endl;
res[x][w] = res[w][x];
}
}
else
{
//i...i+1
assert(SZ(qry) == N);
// cerr << "HELP " << u << ' ' << v << endl;
int x = eid[v][u];
qry.erase(qry.begin() + SZ(cyc) - 2);
int cur = ask(qry);
qry[solved] = x;
mn = ask(qry);
res[u][v] = (mn - cur) + res[cyc[solved]][cyc[solved + 1]];
res[v][u] = res[u][v];
}
//you can do that with a spanning tree!
}
}
D.init();
FOR(u, 0, N)
{
for (int v : edge[u])
{
if (v < u) continue;
if (res[u][v] == 1)
{
ans.PB(eid[u][v]);
D.merge(u, v);
}
}
}
FOR(u, 0, N)
{
for (int v : edge[u])
{
if (u != parent[v]) continue;
if (D.merge(u, v))
{
ans.PB(eid[u][v]);
}
}
}
// cerr << "ANS\n";
// for (int x : ans)
// {
// cerr << x << ' ';
// }
// cerr << endl;
//you can solve a cycle in O(edges)
return ans;
//for each edge:
//if there is a cycle containing it, you can solve everything on the cycle in O(cycle)
//otherwise, you know it's good.
//so if we can decompose the entire tree into cycles/important edges, we get 51
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Correct |
2 ms |
376 KB |
correct |
| 5 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Correct |
2 ms |
376 KB |
correct |
| 5 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Correct |
2 ms |
376 KB |
correct |
| 5 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
3 ms |
376 KB |
correct |
| 3 |
Incorrect |
248 ms |
6376 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 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
376 KB |
correct |
| 4 |
Correct |
2 ms |
376 KB |
correct |
| 5 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
