| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132965 |
2019-07-20T03:02:56 Z |
wilwxk |
Race (IOI11_race) |
C++14 |
|
11 ms |
10488 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
vector<int> g[MAXN], pes[MAXN];
int n, respf;
ll x;
class solution {
public:
int resp=MAXN;
void init() {
tam[n]=0;
memset(prof, 0, sizeof(prof));
solve(0, 1);
}
void solve(int cur, int k) {
basic_scan(cur, cur);
cur=find_centroid(cur, cur, tam[cur]);
prof[cur]=k;
printf(">> %d <<\n", cur);
best.clear(); best[0]={0, 0, n};
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
adv_scan(viz, cur, 1, peso, viz);
}
for(auto cur : best) {
ll d=cur.first;
if(best.find(x-d)==best.end()) continue;
int a=get<2>(cur.second);
int val=get<0>(cur.second);
auto outro=best[x-d];
int b=get<2>(outro);
int val2= b==a ? get<1>(outro) : get<0>(outro);
// printf("d= %lld : %d %d >> %lld + %lld -1\n", d, a, b, val, val2);
resp=min(resp, val+val2);
}
for(auto viz : g[cur]) {
if(prof[viz]) continue;
solve(viz, k+1);
}
}
private:
int tam[MAXN], prof[MAXN];
unordered_map<ll, tuple<int, int, int> > best;
void basic_scan(int cur, int p) {
tam[cur]=1;
for(auto viz : g[cur]) {
if(viz==p||prof[viz]) continue;
basic_scan(viz, cur);
tam[cur]+=tam[viz];
}
}
void melhora(int cur, ll dd, int d) {
if(best.find(dd)==best.end()) {
best[dd]={d, MAXN, cur};
return;
}
int a, b, c; tie(a, b, c)=best[dd];
if(cur==c) best[dd]={min(a, d), b, c};
else if(d<b) best[dd]={a, d, c};
}
void adv_scan(int cur, int p, int d, ll dd, int raiz) {
melhora(raiz, dd, d);
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(viz==p||prof[viz]) continue;
adv_scan(viz, cur, d+1, dd+peso, raiz);
}
}
int find_centroid(int cur, int p, int val) {
int grande=n;
for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz;
if(tam[grande]*2<=val) return cur;
return find_centroid(grande, cur, val);
}
};
int best_path(int N, int K, int H[][2], int L[])
{
n=N; x=K;
for(int i=0; i<n-1; i++) {
int a=H[i][0]; int b=H[i][1];
g[a].push_back(b); pes[a].push_back(L[i]);
g[b].push_back(a); pes[b].push_back(L[i]);
}
solution sol;
sol.init();
respf=sol.resp;
if(respf>n) respf=-1;
return respf;
}
Compilation message
race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
