| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29270 |
2017-07-18T21:26:30 Z |
inqr |
Race (IOI11_race) |
C++14 |
|
6 ms |
5880 KB |
#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define DB printf("debug\n");
using namespace std;
int n,k,ans=1e9;
vector < pair < int , int > > ed[200005];
vector < bool > cenbef(200005,0);
vector < int > subcnt(200005,0);
int sub_count(int vn,int vb){//kendisi dahil
subcnt[vn]=1;
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
if(!cenbef[vnx]&&vnx!=vb){
subcnt[vn]+=sub_count(vnx,vn);
}
}
return subcnt[vn];
}
int find_cen(int vn,int vb,int ts){
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
if(!cenbef[vnx]&&vnx!=vb&&subcnt[vnx]>ts/2)
return find_cen(vnx,vn,ts);
}
return vn;
}
void merge(map<int,int>&a,map<int,int>&b){
map<int,int>::iterator it;
for(it=a.begin();it!=a.end();it++)
if(a.find(k-it->st)!=a.end())
ans=min(ans,a[k-it->st]+it->nd);
for(it=b.begin();it!=b.end();it++)
if(a.find(it->st)==a.end())
a[it->st]=it->nd;
else a[it->st]=min(a[it->st],it->nd);
}
void dfs(int vn,int vb,int rn,int wn,map<int,int>&sbtm){
if(wn>k)return;
if(sbtm.find(wn)==sbtm.end())sbtm[wn]=rn;
else sbtm[wn]=min(sbtm[wn],rn);
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st,edw=ed[vn][i].nd;
if(!cenbef[vnx]&&vnx!=vb)
dfs(vnx,vn,rn+1,wn+edw,sbtm);
}
}
void rou_find(int vn){
map < int , int > allm;
allm[0]=0;
for(int i=0;i<ed[vn].size();i++){
int vnx=ed[vn][i].st;
int edl=ed[vn][i].nd;
if(!cenbef[vnx]){
map < int , int > sbtm;
dfs(vnx,vn,1,edl,sbtm);
merge(allm,sbtm);
}
}
}
void solve(int vn){
sub_count(vn,-1);
int cen=find_cen(vn,-1,subcnt[vn]);
cenbef[cen]=1;
rou_find(cen);
for(int i=0;i<ed[cen].size();i++){
int vnx=ed[cen][i].st;
if(!cenbef[vnx])
solve(vnx);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;k=K;
for(int i=0;i<N-1;i++){
ed[H[i][0]].push_back(make_pair(H[i][1],L[i]));
ed[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
solve(0);
if(ans==1e9)
return -1;
else return ans;
}
Compilation message
race.cpp: In function 'int sub_count(int, int)':
race.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void rou_find(int)':
race.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[vn].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed[cen].size();i++){
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
