| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29405 |
2017-07-19T09:24:05 Z |
kavun |
Race (IOI11_race) |
C++14 |
|
6 ms |
4988 KB |
#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
bool mk[200010];
int n,k;
vii adj[200010];
int sub[200010];
int ans = 1e9;
int subsize(int v, int par)
{
int sum = 0;
for(int i = 0; i < adj[v].size(); i++)
if(adj[v][i].first != par && !mk[adj[v][i].first])
sum += subsize(adj[v][i].first,v);
sub[v] = sum + 1;
return sum + 1;
}
int centroid(int v, int par)
{
for(int i = 0; i < adj[v].size(); i++)
if(adj[v][i].first != par && !mk[adj[v][i].first])
{
int u = adj[v][i].first;
if(sub[u] > n/2)
return centroid(u,v);
}
return v;
}
void dfs(int v, int par, int d, int len, map<int,int>& m)
{
if(m.find(len) != m.end())
m[len] = min(m[len],d);
else
m[len] = d;
for(int i = 0; i < adj[v].size(); i++)
{
int u = adj[v][i].first;
int l = adj[v][i].second;
if(u != par && !mk[u])
dfs(u,v,d+1,len + l, m);
}
}
void solveForCen(int v)
{
map<int,int> mp;
mp[0] = 0;
for(int i = 0;i < adj[v].size(); i++)
{
if(!mk[adj[v][i].first])
{
map<int,int> m;
int u = adj[v][i].first;
dfs(u,v,1,adj[v][i].second,m);
for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
{
int len = it->first;
if(mp.find(k - len) != mp.end())
ans = min(ans,m[len] + mp[k - len]);
if(mp.find(len) != mp.end())
mp[len] = min(mp[len],m[len]);
else
mp[len] = m[len];
}
}
}
}
int solve(int v)
{
subsize(v,v);
int cen = centroid(v,v);
mk[cen] = true;
solveForCen(cen);
for(int i = 0; i < adj[cen].size(); i++)
{
int u = adj[cen][i].first;
if(!mk[u])
solve(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(int i = 0; i < N -1; i++)
{
int v = H[i][0],u = H[i][1],l = L[i];
adj[v].pb(ii(u,l));
adj[u].pb(ii(v,l));
}
solve(0);
if(ans == 1e9)
return -1;
else
return ans;
}
Compilation message
race.cpp: In function 'int subsize(int, int)':
race.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[v].size(); i++)
~~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[v].size(); i++)
~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[v].size(); i++)
~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solveForCen(int)':
race.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < adj[v].size(); i++)
~~^~~~~~~~~~~~~~~
race.cpp: In function 'int solve(int)':
race.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[cen].size(); i++)
~~^~~~~~~~~~~~~~~~~
race.cpp:90:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
