Submission #135346

#	Time	Username	Problem	Language	Result	Execution time	Memory
135346		Talant	Dreaming (IOI13_dreaming)	C++17	47 / 100	125 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];
vector <int> 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;
                  cur = 0,mx = -1;
                  dfs(c);
                  c = cur;
                  mxx = max(mxx,mx);
                  while (c != -1) {
                        res = min(res,max(dis[c],dis[cur] - dis[c]));
                        c = par[c];
                  }
                  ans.pb(res);
            }
      }
      sort(ans.rbegin(),ans.rend());
      if (ans.size() > 1) return max(mxx,ans[0] + ans[1] + l);
      return mxx;
}

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