Submission #1194051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194051		vyaduct	Dreaming (IOI13_dreaming)	C++20	0 / 100	1097 ms	10688 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 100'000;
vector<pair<int,int>> adj[N];
bool visited[N];

void dfs_cc(int s, int e, vector<int> &g){
  g.push_back(s);
  visited[s] = true;
  for (auto [u,w]: adj[s]){
    if (u == e) continue;
    dfs_cc(u, s, g);
  }
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
  for (int i=0;i<N;i++) visited[i] = false;
  for (int i=0;i<m;i++){
    int u = A[i], v = B[i], w = T[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }

  vector<vector<int>> subG;
  for (int i=0;i<n;i++) {
    if (!visited[i]){
      vector<int> cur;
      dfs_cc(i, -1, cur);
      subG.push_back(cur);
    }
  }
  
  int ans=0;
  for (auto G: subG){
    int s = -1, e = -1;
    for (auto x: G){
      if (adj[x].size() == 1){
        if (s == -1) s=x;
        else e=x;
      }
    }
    int par=s;
    int i = s, j = e;
    int sum = adj[i][0].second;
    i = adj[i][0].first;
    while (i != j){
      for (auto [u,w]: adj[i]){
        if (u == par) continue;
        else {
          par = i;
          i = u;
          sum += w;
        }
      }
    }
    i = s, j = e;
    i = adj[i][0].first;
    int ss=0;
    int cur=sum;
    while (i != j){
      for (auto [u,w]: adj[i]){
        if (u == par) continue;
        else {
          par = i;
          i = u;
          ss += w;
          cur = min(cur, max(ss, sum-ss));
        }
      }
    }
    ans += cur;
  }
  return ans + L;;
}

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