제출 #833062

#제출 시각아이디문제언어결과실행 시간메모리
833062idiotcomputer경주 (Race) (IOI11_race)C++11
43 / 100
315 ms102612 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 2*1e5; set<pair<long long int, int>> all[mxN]; int p[mxN]; long long int add[mxN]; int a2[mxN]; int res; int k; void upd(int c){ while (p[c] != p[p[c]]){ p[c] = p[p[c]]; } } void comb(int a, int b){ if (all[a].size() > all[b].size()){ swap(a,b); } for (auto it = all[a].begin(); it != all[a].end(); it++){ long long int val = (*it).first + add[a] - add[b]; int nl = (*it).second + a2[a] - a2[b]; long long int needed = k - val - 2*add[b]; auto it2 = all[b].lower_bound({needed,-1 * 1e9}); if (it2 != all[b].end() && (*it2).first == needed){ res = min(res, nl + (*it2).second + 2 * a2[b]); } all[b].insert({val,nl}); // cout << "HERERE " << a << " "<<b<< ": " << val+add[b] << " " << nl + a2[b] <<'\n'; } p[a] = b; } void dfs(int node, int parent, vector<vector<pair<int,int>>> &connect){ p[node] = node; add[node] = 0; a2[node] = 0; all[node].clear(); int next; for (int i =0; i < connect[node].size(); i++){ next = connect[node][i].first; if (next == parent){ continue; } dfs(next,node,connect); upd(node); upd(next); int a= p[node]; int b = p[next]; add[b] += connect[node][i].second; a2[b] += 1; auto it = all[b].lower_bound({k-add[b],-1*1e9}); if (it != all[b].end() && (*it).first == k-add[b]){ res = min(res, (*it).second + a2[b]); } comb(a,b); } upd(node); all[p[node]].insert({-1*add[p[node]],-1*a2[p[node]]}); /* cout<< node << ":\n"; for (auto it = all[p[node]].begin(); it != all[p[node]].end(); it++){ cout << (*it).first+add[p[node]] << "," << (*it).second+a2[p[node]] << ' '; } cout << '\n';*/ } int best_path(int n,int ck, int h[][2], int l[]){ vector<vector<pair<int,int>>> connect(n); k = ck; for (int i =0; i < n-1; i++){ connect[h[i][0]].push_back({h[i][1],l[i]}); connect[h[i][1]].push_back({h[i][0],l[i]}); } /* for (int i =0; i < n; i++){ cout << i << ": "; for (int j = 0; j < connect[i].size();j++){ cout<<connect[i][j].first<<","<<connect[i][j].second<<" "; } cout<<'\n'; }*/ res = 1e9; dfs(0,-1,connect); if (res == 1e9){ return -1; } return res; }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void dfs(int, int, std::vector<std::vector<std::pair<int, int> > >&)':
race.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i =0; i < connect[node].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...