Submission #253389

#	Time	Username	Problem	Language	Result	Execution time	Memory
253389		ChrisT	Race (IOI11_race)	C++17	100 / 100	1073 ms	37356 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef pair<int,int> pii;
vector<pii> adj[200001],nw;
int sz[200001], ans,k;
int H[200001][2], L[200001];
bool centroid[200001];
map<int,int> mindist;
int dist[200001], len[200001];
int dfs (int cur ,int p) {
  sz[cur] = 1;
  for (pii i : adj[cur]) if(i.first != p && !centroid[i.first]) sz[cur] += dfs(i.first,cur);
  return sz[cur];
}
void firstlength (int cur, int par, int down, int length) {
  if (mindist.find(down) == mindist.end() || length < mindist[down])
  mindist[down] = length;
  if (down == k) ans = min(ans,length);
  for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) firstlength(p.first,cur,down+p.second,length+1);
}
void findlength (int cur ,int par ,int down, int length) {
  if (down == k) ans = min(ans,length);
  if (mindist.find(down) == mindist.end() || mindist[down] > length) nw.push_back({down,length});
  if (mindist.find(k-down) != mindist.end()) ans = min(ans,length+mindist[k-down]);
  for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) findlength(p.first,cur,down+p.second,length+1);
}
int findCentroid (int cur, int p, int n) {
  for (pii i : adj[cur]) 
    if (i.first != p && !centroid[i.first] && sz[i.first] > (n>>1))
    return findCentroid (i.first,cur,n);
  return cur;
}
void solve (int cur) {
  dfs(cur,-1);
  int cent = findCentroid(cur,-1,sz[cur]);
  centroid[cent] = 1;
  mindist.clear();
  int i;
  for (i = 0; i < adj[cent].size() ; i++) if (!centroid[adj[cent][i].first]) {firstlength(adj[cent][i].first,cent,adj[cent][i].second,1); break;}
  for (i++; i < adj[cent].size(); i++) if (!centroid[adj[cent][i].first]) {
    findlength(adj[cent][i].first,cent,adj[cent][i].second,1);
    while (!nw.empty()) mindist[nw.back().first] = nw.back().second, nw.pop_back();
  }
  for (pii p : adj[cent]) if (!centroid[p.first]) solve(p.first);
}
int best_path(int n, int K, int h[][2], int l[]) {
  k=K;
  for (int i = 0; i < n-1; i++) {
    adj[h[i][0]].push_back({h[i][1],l[i]});
    adj[h[i][1]].push_back({h[i][0],l[i]});
  }
  ans = INT_MAX;
  solve(0);
  return ans == INT_MAX ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < adj[cent].size() ; i++) if (!centroid[adj[cent][i].first]) {firstlength(adj[cent][i].first,cent,adj[cent][i].second,1); break;}
               ~~^~~~~~~~~~~~~~~~~~
race.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i++; i < adj[cent].size(); i++) if (!centroid[adj[cent][i].first]) {
             ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57