Submission #29267

#TimeUsernameProblemLanguageResultExecution timeMemory
29267inqrRace (IOI11_race)C++14
0 / 100
7 ms5880 KiB
#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=INT_MAX; 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>&allm,map<int,int>&sbtm){ map<int,int>::iterator it; for(it=sbtm.begin();it!=sbtm.end();it++){ if(allm.find(k-it->st)!=allm.end()){ ans=min(ans,allm[k-it->st]+it->nd); } } for(it=sbtm.begin();it!=sbtm.end();it++){ if(allm.find(it->st)==allm.end()){ allm[it->st]=it->nd; } else{ allm[it->st]=min(allm[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[vn].size();i++){ int vnx=ed[vn][i].st; if(!cenbef[vnx]) rou_find(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==INT_MAX) return -1; else return ans; }

Compilation message (stderr)

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:52: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:61: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:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
              ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...