| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 103644 |
2019-04-01T16:29:08 Z |
CPX |
Race (IOI11_race) |
C++14 |
|
8 ms |
6272 KB |
#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define setDP(arr) memset(arr,-1,sizeof arr)
#define Clear(arr) memset(arr,0,sizeof arr)
#define oo 1000000000
#define inf 1000000000000000000
#define P1 31
#define P2 37
#define M 1000000007
#define M2 1000000009
#define pii pair<ll,ll>
typedef long long ll;
using namespace std;
const int N = 255001;
const int SQRTN = 320;
const int LOGN = 20;
const long double PI = acos(-1);
const long double TAU = 2*PI;
int n , k,ans = oo,h[100][2],l[100],sz;
vector<pair<int,int> > g[N];
bool vis[N];
vector<int> centroid,v;
map<int,vector<int> > mp;
map<int,vector<int> >::iterator it;
int getSize(int n , int p=-1){
int ret = 1;
for(int i = 0 ; i < g[n].size() ; i++){
if(vis[g[n][i].F]||g[n][i].F==p)continue;
ret+=getSize(g[n][i].F,n);
}
return ret;
}
int getCentroid(int node = 0, int p = -1){
bool f = 1;
int s = 1,t;
for(int i=0;i<g[node].size();i++){
if (g[node][i].F == p || vis[g[node][i].F])continue;
t=getCentroid(g[node][i].F,node);
if(t>sz>>1)
f = 0;
s += t;
}
if((sz - s)<<1 >sz)f = 0;
if(f)centroid.push_back(node);
return s;
}
void dfs(int node, int d1=0, int d2=0 , int p=-1){
mp[d1].push_back(d2);
for(int i = 0 ; i < g[node].size() ; i++){
if(g[node][i].F==p||vis[g[node][i].F])continue;
dfs(g[node][i].F,d1+g[node][i].S,d2+1,node);
}
}
void calc(){
int x=0;
for(it = mp.begin() ; it != mp.end() ; it++){
sort(all(it->S));
}
for(it = mp.begin() ; it != mp.end() ; it++){
x=it->F;
if((x<<1)>k)break;
if(mp.find(k-x)==mp.end())continue;
if(k==(x<<1)){
if((it->S).size()>1){
ans = min(ans,(it->S)[0]+(it->S)[1]);
}
}else{
ans=min(ans,(it->S)[0]+mp[k-x][0]);
}
}
}
void centroidDecomposiotion(int node = 0){
sz = getSize(node);
if(sz==1)return;
getCentroid(node);
int root = centroid[0];
centroid.clear();
dfs(root);
calc();
mp.clear();
vis[root]=1;
for(int i = 0 ; i < g[root].size() ; i++){
if(!vis[g[root][i].F])
centroidDecomposiotion(g[root][i].F);
}
}
int best_path(int n , int k , int h[][2], int l[]){
::n = n;
::k = k;
for(int i = 0 ; i < n-1 ; i++){
g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
}
centroidDecomposiotion(0);
return ans;
}
Compilation message
race.cpp: In function 'int getSize(int, int)':
race.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < g[n].size() ; i++){
~~^~~~~~~~~~~~~
race.cpp: In function 'int getCentroid(int, int)':
race.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[node].size();i++){
~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < g[node].size() ; i++){
~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void centroidDecomposiotion(int)':
race.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < g[root].size() ; i++){
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
