Submission #710482

#TimeUsernameProblemLanguageResultExecution timeMemory
710482aggrovectorRace (IOI11_race)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; int n,k,x,y,w,used[200005],vi[200005],fa[200005],subtree[200005],d[200005],d1[200005]; unsigned int i,j; long long ans; vector<pair<int,int>> v[200005]; vector<int> centroids; unordered_map<int,int> cnt,cnt1; bool flag,iscentroid; const long long INF=1e15; void dfs(int x, int f) {//subtree size vi[x]=1; fa[x]=f; for (unsigned int i=0;i<v[x].size();i++) { if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) { d1[v[x][i].first]=d1[x]+1; dfs(v[x][i].first,f); subtree[x]+=subtree[v[x][i].first]; } } subtree[x]++; } void dfs1(int x) {//distance by length and number of nodes vi[x]=1; for (unsigned int i=0;i<v[x].size();i++) { if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) { d[v[x][i].first]=d[x]+v[x][i].second; d1[v[x][i].first]=d1[x]+1; dfs1(v[x][i].first); } } } void dfs2(int x, int f) { vi[x]=1; if (cnt.find(k-d[x])!=cnt.end()) { ans=min(ans,(long long)cnt[k-d[x]]+d1[x]); } if (cnt1.find(d[x])==cnt1.end()) { cnt1[d[x]]=d1[x]; } else { cnt1[d[x]]=min(cnt1[d[x]],d1[x]); } for (unsigned int i=0;i<v[x].size();i++) { if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) { dfs2(v[x][i].first,f); if (x==f) { // cout << "x,i: " << x << ' ' << i << endl; // cout << "cnt1: " << endl; // for (auto it=cnt1.begin();it!=cnt1.end();it++) { // cout << it->first << ' ' << it->second << endl; // } // cout << "cnt: " << endl; for (auto it=cnt1.begin();it!=cnt1.end();it++) { if (cnt.find(it->first)==cnt.end()) { cnt[it->first]=it->second; } else { cnt[it->first]=min(cnt[it->first],it->second); } } // for (auto it=cnt.begin();it!=cnt.end();it++) { // cout << it->first << ' ' << it->second << endl; // } cnt1.clear(); } } } } int main() { // ifstream fin("P4149_5.in"); ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (i=1;i<n;i++) { cin >> x >> y >> w; v[x].emplace_back(y,w); v[y].emplace_back(x,w); } ans=INF; int cntt=0; while(true) { cntt++; flag=true; for (i=0;i<n;i++) { subtree[i]=0; vi[i]=0; fa[i]=0; d1[i]=0; } // cout << 1111 << endl; for (i=0;i<n;i++) { if (used[i]==0 && vi[i]==0) { flag=false; dfs(i,i); } } // cout << 2222 << endl; // cout << "subtree: "; // for (i=0;i<n;i++) { // cout << subtree[i] << ' '; // } // cout << endl; // cout << "fa: "; // for (i=0;i<n;i++) { // cout << fa[i] << ' '; // } // cout << endl; if (flag) { break; } centroids.clear(); for (i=0;i<n;i++) { if (used[i]==1) { continue; } iscentroid=true; for (j=0;j<v[i].size();j++) { if (d1[v[i][j].first]>d1[i] && subtree[v[i][j].first]>subtree[fa[i]]/2) { iscentroid=false; } } if (subtree[fa[i]]-subtree[i]>subtree[fa[i]]/2) { iscentroid=false; } if (iscentroid) { centroids.push_back(i); } } // cout << "centroids: "; // for (i=0;i<centroids.size();i++) { // cout << centroids[i] << ' '; // } // cout << endl; for (i=0;i<n;i++) { d[i]=0; d1[i]=0; vi[i]=0; } for (i=0;i<centroids.size();i++) { if (vi[centroids[i]]==0) { dfs1(centroids[i]); } } // cout << "d: "; // for (i=0;i<n;i++) { // cout << d[i] << ' '; // } // cout << endl; // cout << "d1: "; // for (i=0;i<n;i++) { // cout << d1[i] << ' '; // } // cout << endl; for (i=0;i<n;i++) { vi[i]=0; } for (i=0;i<centroids.size();i++) { if (vi[centroids[i]]==0) { cnt.clear(); cnt1.clear(); dfs2(centroids[i],centroids[i]); used[centroids[i]]=1; } } // cout << "used: "; // for (i=0;i<n;i++) { // cout << used[i] << ' '; // } // cout << endl; // cout << "ans: " << ans << endl << endl; } if (ans==INF) { cout << -1 << endl; } else { cout << ans << endl; } // cout << cntt << endl; }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:79:12: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   79 |  for (i=1;i<n;i++) {
      |           ~^~
race.cpp:89:13: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   89 |   for (i=0;i<n;i++) {
      |            ~^~
race.cpp:96:13: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   96 |   for (i=0;i<n;i++) {
      |            ~^~
race.cpp:117:13: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
  117 |   for (i=0;i<n;i++) {
      |            ~^~
race.cpp:139:13: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
  139 |   for (i=0;i<n;i++) {
      |            ~^~
race.cpp:159:13: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
  159 |   for (i=0;i<n;i++) {
      |            ~^~
/usr/bin/ld: /tmp/cc4xnl0Y.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnQ3NgW.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccnQ3NgW.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status