Submission #135358

#	Time	Username	Problem	Language	Result	Execution time	Memory
135358		Talant	Dreaming (IOI13_dreaming)	C++17	100 / 100	202 ms	35704 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int NN = (1e6 + 5);
const int inf = (1e9 + 7);

int n,m,l;
int par[NN],dis[NN],u[NN];
int mx = -1;
int mxx;
int cur;
vector <pair<int,int> > g[NN],ans;

void dfs (int v,int d = 0,int p = -1) {
      u[v] = 1;
      par[v] = p;
      dis[v] = d;

      if (mx < d) mx = d,cur = v;
      for (auto to : g[v]) {
            if (to.fr != p) dfs(to.fr,d + to.sc,v);
      }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
      n = N,m = M,l = L;
      for (int i = 0; i < m; i ++) {
            A[i] ++;
            B[i] ++;
            g[A[i]].pb(mk(B[i],T[i]));
            g[B[i]].pb(mk(A[i],T[i]));
      }
      for (int i = 1; i <= n; i ++) {
            if (!u[i]) {
                  cur = 0,mx = -1;
                  dfs(i);
                  mxx = max(mxx,mx);
                  int c = cur,res = inf,id = 0;
                  cur = 0,mx = -1;
                  dfs(c);

                  c = cur;
                  mxx = max(mxx,mx);
                  while (c != -1) {
                        if (res > max(dis[c],dis[cur] - dis[c])) res = max(dis[c],dis[cur] - dis[c]),id = c;
                        c = par[c];
                  }
                  ans.pb(mk(res,id));
            }
      }
      sort(ans.rbegin(),ans.rend());
      for (int i = 1; i < ans.size(); i ++) {
            g[ans[0].sc].pb(mk(ans[i].sc,l));
            g[ans[i].sc].pb(mk(ans[0].sc,l));
      }
      cur = 0,mx = -1;
      dfs(1);
      mx = -1;
      dfs(cur);
      return mx;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:58:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 1; i < ans.size(); i ++) {
                       ~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23