| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16415 |
2015-08-23T07:02:58 Z |
comet |
Race (IOI11_race) |
C++ |
|
5 ms |
4360 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define pb push_back
using namespace std;
struct edge{
int u,c;
};
struct state{
int v,c,len;
};
typedef long long ll;
typedef vector<int> vec;
typedef vector<edge> Evec;
vector<Evec> path;
int N,K;
int a[1000010];
int SubSz[200000],MaxSz[200000];
bool cover[200000],chk[200000];
int dfs(int v){
chk[v]=1;
SubSz[v]=MaxSz[v]=1;
for(int i=0;i<path[v].size();i++){
int u=path[v][i].u;
if(!chk[u]&&!cover[u]){
int t=dfs(u);
SubSz[v]+=t;
MaxSz[v]=max(MaxSz[v],t+1);
}
}
return SubSz[v];
}
int centroid(int root,int cnt){
dfs(root);
int Min=1e9,ret;
for(int i=0;i<N;i++){
if(chk[i]&&!cover[i]){
if(Min>max(MaxSz[i],cnt-MaxSz[i])){
Min=max(MaxSz[i],cnt-MaxSz[i]);
ret=i;
}
chk[i]=0;
}
}
return ret;
}
int f(int root,int cnt){
if(cnt==1)return 1e9;
root=centroid(root,cnt);
cover[root]=1;
int ret=1e9;
/*printf("root : %d\n",root);
for(int i=0;i<N;i++)printf("%d ",cover[i]);puts("");
for(int i=0;i<N;i++)printf("%d ",chk[i]);puts("");*/
for(int i=0;i<path[root].size();i++){
int nxt=path[root][i].u;
int cost=path[root][i].c;
if(cover[nxt])continue;
ret=min(ret,f(nxt,SubSz[nxt]));
//printf("%d-->%d : %d\n",root,nxt,ret);
}
for(int i=0;i<path[root].size();i++){
int nxt=path[root][i].u;
int cost=path[root][i].c;
if(cover[nxt])continue;
queue<state> Q;
Q.push(state{nxt,cost,1});
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c>K)continue;
ret=min(ret,a[K-h.c]+h.len);
for(int j=0;j<path[h.v].size();j++){
int u=path[h.v][j].u;
if(!cover[u]&&!chk[u]){
chk[u]=1;
Q.push(state{u,h.c+path[h.v][j].c,h.len+1});
}
}
}
Q.push(state{nxt,cost,1});
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c>K)continue;
if(h.c==K)ret=min(ret,h.len);
a[h.c]=min(a[h.c],h.len);
for(int j=0;j<path[h.v].size();j++){
int u=path[h.v][j].u;
if(!cover[u]&&chk[u]){
chk[u]=0;
Q.push(state{u,h.c+path[h.v][j].c,h.len+1});
}
}
}
}
for(int i=0;i<path[root].size();i++){
int nxt=path[root][i].u;
int cost=path[root][i].c;
if(cover[nxt])continue;
queue<state> Q;
Q.push(state{nxt,cost,1});
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c>K)continue;
for(int j=0;j<path[h.v].size();j++){
int u=path[h.v][j].u;
if(!cover[u]&&!chk[u]){
chk[u]=1;
Q.push(state{u,h.c+path[h.v][j].c,h.len+1});
}
}
}
Q.push(state{nxt,cost,1});
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c>K)continue;
a[h.c]=1e9;
for(int j=0;j<path[h.v].size();j++){
int u=path[h.v][j].u;
if(!cover[u]&&chk[u]){
chk[u]=0;
Q.push(state{u,h.c+path[h.v][j].c,h.len+1});
}
}
}
}
cover[root]=0;
return ret;
}
int best_path(int N_,int K_,int H[][2],int L[]){
N=N_,K=K_;
memset(a,0x3f,sizeof(a));
path.assign(N,Evec());
for(int i=0;i<N-1;i++){
path[H[i][0]].pb(edge{H[i][1],L[i]});
path[H[i][1]].pb(edge{H[i][0],L[i]});
}
int ret=f(0,N);
if(ret>N)return -1;
return ret;
}
Compilation message
race.cpp: In function 'int dfs(int)':
race.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[v].size();i++){
~^~~~~~~~~~~~~~~
race.cpp: In function 'int f(int, int)':
race.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[root].size();i++){
~^~~~~~~~~~~~~~~~~~
race.cpp:66:7: warning: unused variable 'cost' [-Wunused-variable]
int cost=path[root][i].c;
^~~~
race.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[root].size();i++){
~^~~~~~~~~~~~~~~~~~
race.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<path[h.v].size();j++){
~^~~~~~~~~~~~~~~~~
race.cpp:101:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<path[h.v].size();j++){
~^~~~~~~~~~~~~~~~~
race.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[root].size();i++){
~^~~~~~~~~~~~~~~~~~
race.cpp:122:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<path[h.v].size();j++){
~^~~~~~~~~~~~~~~~~
race.cpp:136:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<path[h.v].size();j++){
~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:51:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ret;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
4360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
