| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 953908 |
2024-03-26T21:22:18 Z |
ArtieAaron |
Race (IOI11_race) |
C++14 |
|
2 ms |
8792 KB |
#include <bits/stdc++.h>
using namespace std;
typedef int lli;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
#define f first
#define s second
#define pb push_back
#define sz(v) (v).size()
#define all(v) sort((v).begin(), (v).end())
#define rall(v) sort((v).rbegin(), (v).rend())
#define SL '\n'
#define fore(a,s,d) for(lli a = (s), asd = (d); a < asd; a ++)
#define wd(a,s) fore(a,0,s)
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const lli NN = 2e5;
lli vis[NN], rk[NN], curvis = 0;
lli n, k;
vii adj[NN];
bool err[NN];
lli dfs_rk(lli pos){
// calcule los rangos desde una raíz random
vis[pos] = curvis, rk[pos] = 1;
for(auto i: adj[pos]){
if(vis[i.f] == curvis or err[i.f]) continue;
rk[pos] += dfs_rk(i.f);
}
return rk[pos];
}
lli dfs_cn(lli pos, lli x){
// encuentre el centroide
vis[pos] = curvis;
ii mx = {-1e18, -1};
for(auto i: adj[pos]){
if(vis[i.f] == curvis or err[i.f]) continue;
if(mx.f < rk[i.f]){
mx.f = rk[i.f], mx.s = i.f;
}
}
if(mx.f > x/2) return dfs_cn(mx.s, x);
return pos;
}
void dfs_pa(lli pos, ii ans, vii &gans){
// agrege las aristas mínimas para cada valor posible del sub-grafo
// regresa peso, #aristas
vis[pos] = curvis;
for(auto i: adj[pos]){
if(vis[i.f] == curvis or err[i.f]) continue;
ii lans = ii({ans.f + i.f, ans.s + 1});
gans.pb(lans);
dfs_pa(i.f, lans, gans);
}
return;
}
lli cmna(vii v){
// calcula el camino mas corto por iteración
lli ans = 1e18;
for(auto i: v){
if(vis[i.f] == curvis) continue;
lli pos = 1, s = lli(sz(v)) - 2;
while(s){
while(pos + s < lli(sz(v)) and v[pos + s].f <= k - i.f) pos += s;
s /= 2;
}
if(v[pos].f + i.f == k){
ans = min(ans, v[pos].s + i.s);
vis[i.f] = vis[v[pos].f] = curvis;
}
}
return ans;
}
lli best_path(lli N, lli K, lli H[][2], lli L[]){
// re-escribir entrada
{
n = N, k = K;
wd(i,n-1){
adj[H[i][0]].pb(ii({H[i][1], L[i]}));
adj[H[i][1]].pb(ii({H[i][0], L[i]}));
}
}
lli ans = 1e18;
queue<lli> q; q.push(0); err[0] = true;
while(!q.empty()){
lli o = q.front();
q.pop();
curvis = (curvis + 1) % lli(1e18);
dfs_rk(o);
curvis = (curvis + 1) % lli(1e18);
lli cn = dfs_cn(o, rk[o]);
// 3/2 * n
curvis = (curvis + 1) % lli(1e18);
vii paths = {};
dfs_pa(cn, ii({0, 0}), paths);
// + n
all(paths);
// + n log(n)
vii spth = {};
for(auto i: paths)
if(sz(spth) == 0 or spth[lli(sz(spth))-1].f != i.f) spth.pb(i);
err[cn] = true;
curvis = (curvis + 1) % lli(1e18);
lli mn = cmna(spth);
// + n log(n)
ans = min(ans, mn);
for(auto i: adj[cn]){
if(err[i.f]) continue;
q.push(i.f);
}
}
// + (push + insert) * n
if(ans == 1e18) return -1;
return ans;
}
Compilation message
race.cpp: In function 'lli cmna(vii)':
race.cpp:64:15: warning: overflow in conversion from 'double' to 'lli' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
64 | lli ans = 1e18;
| ^~~~
race.cpp: In function 'lli best_path(lli, lli, lli (*)[2], lli*)':
race.cpp:89:15: warning: overflow in conversion from 'double' to 'lli' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
89 | lli ans = 1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
