| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 103007 |
2019-03-28T14:58:46 Z |
hugo_pm |
Race (IOI11_race) |
C++17 |
|
34 ms |
29048 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const int BIG = (int)(1e9);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int borne = 201*1000;
const int lgb = 19;
int nbNoeuds, somVoulue;
vector<pii> adj[borne];
int anc[borne][lgb];
int se[borne][lgb];
// ROOT
int par[borne], dep[borne], dse[borne];
void dfsInit(int nod)
{
form2(i, 1, lgb) {
int tmp = anc[nod][i-1];
if (tmp == -1) anc[nod][i] = -1;
else {
anc[nod][i] = anc[tmp][i-1];
}
}
for (pii vor : adj[nod]) if (vor.fi != anc[nod][0]) {
int vo = vor.fi;
anc[vo][0] = nod;
dep[vo] = dep[nod] + 1;
dse[vo] = dse[nod] + vor.se;
dfsInit(vo);
}
}
int lca(int u, int v)
{
if (u == v) return u;
if (dep[u] < dep[v]) return lca(v, u);
ford(i, lgb) {
int kc = (1 << i);
if (dep[u] - dep[v] >= kc && anc[u][i] != -1) {
u = anc[u][i];
}
}
assert(dep[u] == dep[v]);
if (u == v) return u;
ford(i, lgb) {
int nu = anc[u][i], nv = anc[v][i];
if (nu != nv && nu != -1 && nv != -1) { u = nu; v = nv; }
}
assert(u != v);
assert(anc[u][0] == anc[v][0]);
return anc[u][0];
}
int nbEdges(int u, int v)
{
int art = lca(u, v);
int d1 = dep[u] - dep[art];
int d2 = dep[v] - dep[art];
assert(d1 >= 0 && d2 >= 0);
return d1+d2;
}
int sumEdges(int u, int v)
{
int art = lca(u, v);
int d1 = dse[u] - dse[art];
int d2 = dse[v] - dse[art];
assert(d1 >= 0 && d2 >= 0);
return d1+d2;
}
// Cendec
bool bloque[borne];
int cpar[borne];
int csz[borne];
void dfsInfos(int nod)
{
csz[nod] = 1;
for (auto vor : adj[nod]) {
int vo = vor.fi;
if (vo == cpar[nod] || bloque[vo]) continue;
cpar[vo] = nod;
dfsInfos(vo);
csz[nod] += csz[vo];
}
}
int findCen(int nod, int tot)
{
int st = 0;
int mk = -BIG, be=-1;
for (auto vor : adj[nod]) {
int vo = vor.fi;
if (vo == cpar[nod] || bloque[vo]) continue;
st += csz[vo];
if (csz[vo] > mk) {
mk = csz[vo];
be = vo;
}
}
int reste = tot-1-st;
if (mk <= (tot+1)/2 && reste <= (tot+1)/2) {
return nod;
} else if (be != -1) {
return findCen(be, tot);
}
return -1;
}
vector<int> cen[borne];
int cenroot=-1;
int cenDec(int from, int vers, int tot)
{
cpar[vers] = -1;
dfsInfos(vers);
int nod = findCen(vers, tot);
if (cenroot == -1) cenroot = nod;
bloque[nod] = true;
int st=0;
vector<pii> toproc;
for (auto vor : adj[nod]) {
int vo = vor.fi;
if (vo == cpar[nod] || bloque[vo]) continue;
st += csz[vo];
toproc.push_back({vo, csz[vo]});
}
if (cpar[nod] != -1) {
int reste=tot-1-st;
if (reste != 0) toproc.push_back({cpar[nod], reste});
}
for (auto x : toproc) {
int res = cenDec(nod, x.fi, x.se);
cen[nod].push_back(res);
}
return nod;
}
vector<int> enfants[borne];
int rep = BIG;
void proc(int nod)
{
enfants[nod].push_back(nod);
set<pii> tc;
tc.insert({0,0});
for (int enf : cen[nod]) {
proc(enf);
for (int x : enfants[enf]) {
enfants[nod].push_back(x);
int ss = sumEdges(nod, x);
int ne = nbEdges(nod, x);
int req = somVoulue - ss;
auto it2 = tc.lower_bound({req, -1});
if (it2 != tc.end() && it2->fi == req) {
chmin(rep, ne + it2->se);
}
}
for (int x : enfants[enf]) {
tc.insert({sumEdges(nod, x), nbEdges(nod, x)});
}
}
}
int solve()
{
anc[0][0] = -1;
dfsInit(0);
cenDec(-1, 0, nbNoeuds);
proc(cenroot);
if (rep == BIG) rep = -1;
return rep;
}
int best_path(int N, int K, int H[][2], int L[])
{
nbNoeuds = N;
somVoulue = K;
form(i, N) {
int u = H[i][0], v = H[i][1];
int p = L[i];
adj[u].push_back({v,p});
adj[v].push_back({u,p});
}
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
