| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 109743 |
2019-05-07T21:10:13 Z |
m3r8 |
Race (IOI11_race) |
C++14 |
|
6 ms |
5120 KB |
#include <stdio.h>
#include "race.h"
#include <utility>
#include <string.h>
#include <vector>
#define ll long long
#define ii std::pair<int,int>
#define il std::pair<int,std::pair<int,std::pair<int,long long>>>
#define N 200100
#define K 1000000
std::vector<il> adj[N];
int cnt;
int child[N];
int posNxt[N];
ii isDist[K];
ll dist[N];
int nKant[N];
int szSub[N];
ll k;
ll mn;
int trr;
void dfsSub(int v, int p){
szSub[v] = 0;
for(auto &edg: adj[v]){
int u = edg.first;
if(u != p && edg.second.first){
dfsSub(u,v);
szSub[v] += 1;
szSub[v] += szSub[u];
};
};
};
int findCent(int root, int par){
dfsSub(root, par);
int sz = szSub[root] + 1;
int akt = root;
int prev = par;
int mx = 0;
int nxt = -1;
while(true){
nxt = akt;
mx = sz - szSub[akt] - 1;
for(auto& edg:adj[akt]){
if(edg.first != prev && edg.second.first){
if(mx < szSub[edg.first]+1){
mx = szSub[edg.first]+1;
nxt = edg.first;
};
};
};
if(mx <= (sz/2)){
return akt;
}
else{
prev = akt;
akt = nxt;
};
};
};
void dfsST(int v, int par, ll cst, int num){
ll d = cst + dist[par];
dist[v] = d;
int knt = nKant[par] +1;
nKant[v] = knt;
child[cnt++] = v;
ll srch = k-d;
if(srch >= 0 && isDist[srch].first == num){
if(mn == -1 || mn > isDist[srch].second + knt){
mn = isDist[srch].second + knt;
};
};
for(auto &edg:adj[v]){
if(edg.first != par && edg.second.first){
dfsST(edg.first,v,cst+edg.second.second.second,num);
};
};
};
void goFromCen(int cen){
trr++;
dist[cen] = 0;
nKant[cen] = 0;
for(auto &edg: adj[cen]){
if(edg.second.first){
edg.second.first = 0;
adj[edg.first][edg.second.second.first].second.first = 0;
cnt = 0;
dfsST(edg.first,cen,edg.second.second.second,trr);
for(int i = 0;i<cnt;i++){
if(isDist[dist[child[i]]].first != trr){
isDist[dist[child[i]]].first = trr;
isDist[dist[child[i]]].second = nKant[child[i]];
}else if(isDist[dist[child[i]]].second > nKant[child[i]]){
isDist[dist[child[i]]].second = nKant[child[i]];
};
};
edg.second.first = 1;
};
};
for(auto &edg:adj[cen]){
if(edg.second.first){
edg.second.first = 0;
int nxtC = findCent(edg.first,cen);
goFromCen(nxtC);
};
};
};
int n;
int best_path(int n1,int k1,int H[][2],int L[]){
int a,b;
n = n1;
k=k1;
ll cst;
for(int i = 0;i<n-1;i++){
a = H[i][0];
b = H[i][1];
cst = L[i];
a++;
b++;
int sa = adj[a].size();
int sb = adj[b].size();
adj[a].push_back(il(0,std::pair<int,std::pair<int,long long>>(0,std::pair<int,long long>(0,0))));
adj[a][sa].first = b;
adj[a][sa].second.first = 1;
adj[a][sa].second.second.first = sb;
adj[a][sa].second.second.second = cst;
adj[b].push_back(il(0,std::pair<int,std::pair<int,long long>>(0,std::pair<int,long long>(0,0))));
adj[b][sb].first = a;
adj[b][sb].second.first = 1;
adj[b][sb].second.second.first = sa;
adj[b][sb].second.second.second = cst;
};
mn = -1;
cnt = 0;
trr = 1;
int c1 = findCent(1,-1);
goFromCen(c1);
return mn;
return 0;
};
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
