제출 #281933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281933		kevlee	Dreaming (IOI13_dreaming)	C++17	18 / 100	342 ms	26864 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int dist[100005], deg[100005], n, m, l, diameter, ans, sz;
vp edges[100005];
vi v, comp;
bool vis[100005], pushed[100005];
multiset <int> weight[100005];
void dfs(int x, int p) {
  diameter = max(diameter, dist[x]);
  vis[x] = true;
  v.pb(x);
  for (auto edge: edges[x]) {
    if (edge.fi != p) {
      dist[edge.fi] = dist[x] + edge.se;
      dfs(edge.fi, x);
    }
  }
}
int find_diameter(int root) {
  dist[root] = 0;
  diameter = 0;
  sz = 0;
  v.clear();
  dfs(root, -1);
  return diameter;
}
void find_shortest_path() {
  priority_queue <pii, vector<pii>, greater<pii> > pq;
  for (int node: v) {
    if (deg[node] == 1) {
      pq.push({edges[node][0].se, node});
      pushed[node] = true;
      deg[node] = 0;
    }
  }
  int sz = v.size();
  while (sz > 2) {
    pii cur = pq.top();
    pq.pop();
    cout << cur.fi << ' ' << cur.se << endl;
    sz--;
    for (auto edge: edges[cur.se]) {
      deg[edge.fi]--;
      weight[edge.fi].erase(weight[edge.fi].find(edge.se));
      if (deg[edge.fi] == 1) {
        //assert((int)weight[edge.fi].size() == 1);
        pq.push({*weight[edge.fi].begin(), edge.fi});
        pushed[edge.fi] = true;
      }
    }
  }
  int tmp = inf*2;
  while (!pq.empty()) {
    pii cur = pq.top();
    pq.pop();
    tmp = min(tmp, find_diameter(cur.se));
  }
  for (int node: v) {
    if (!pushed[node]) {
      tmp = min(tmp, find_diameter(node));
    }
  }
  comp.pb(tmp);
}
int travelTime(int N, int M, int L, int u[], int v[], int t[]) {
  n = N;
  m = M;
  l = L;
  FOR(i, 0, m-1) {
    edges[u[i] + 1].emplace_back(v[i] + 1, t[i]);
    edges[v[i] + 1].emplace_back(u[i] + 1, t[i]);
    deg[u[i] + 1]++;
    deg[v[i] + 1]++;
    weight[u[i] + 1].insert(t[i]);
    weight[v[i] + 1].insert(t[i]);
  }
  FOR(i, 1, n) {
    if (!vis[i]) {
      ans = max(ans, find_diameter(i));
      find_shortest_path();
    }
  }
  int sz = comp.size();
  sort(all(comp));
  reverse(all(comp));
  if (sz == 1) {}
  else if (sz == 2) {
    ans = max(ans, L + comp[0] + comp[1]);
  } else {
    ans = max(ans, L + comp[0] + comp[1]);
    ans = max(ans, L + L + comp[1] + comp[2]);
  }
  return ans;
}

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