Submission #1279651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279651		janson0109	Dreaming (IOI13_dreaming)	C++20	100 / 100	61 ms	21388 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 1000000007;

void dfs(int n, int root, vector<vector<pair<int,int>>> &e, vector<int> &dist, vector<bool> &visited, vector<int> &vis, int cur, bool add) {
    dist[root] = cur;
    visited[root] = 1;
    if(add) vis.push_back(root);
    for(auto & v : e[root]) if(!visited[v.F]) dfs(n, v.F, e, dist, visited, vis, cur+v.S, add);
}

pair<int,int> rd(int n, int root, vector<vector<pair<int,int>>> &e, vector<int> &dist1, vector<int> &dist2, vector<int> &dist3, vector<bool> &v1, vector<bool> &v2, vector<bool> &v3) {
    vector<int> vis;
    dfs(n, root, e, dist1, v1, vis, 0, 1);
    int m1 = root;
    for(auto & x : vis) if(dist1[x] > dist1[m1]) m1=x;
    dfs(n, m1, e, dist2, v2, vis, 0, 0);
    int m2 = m1;
    for(auto & x : vis) if(dist2[x] > dist2[m2]) m2=x;
    dfs(n, m2, e, dist3, v3, vis, 0, 0);
    int r = INT_MAX;
    for(auto & x : vis) r = min(max(dist2[x], dist3[x]), r);
    return make_pair(r, dist2[m2]);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int,int>>> e(N);
    for(int i=0; i<M; i++) {
        e[A[i]].push_back(make_pair(B[i], T[i]));
        e[B[i]].push_back(make_pair(A[i], T[i]));
    }
    vector<int> dist1(N), dist2(N), dist3(N); vector<bool> v1(N,0), v2(N,0), v3(N,0);
    vector<int> radii; int maxd=0;
    for(int i=0; i<N; i++) {
        if(v1[i]) continue;
        pair<int,int> d= rd(N, i, e, dist1, dist2, dist3, v1, v2, v3);
        radii.push_back(d.F); maxd = max(maxd, d.S);
    }
    sort(radii.begin(), radii.end());
    ll k = radii.size();
    return max(maxd, k == 1 ? 0 : (k == 2 ? radii[0] + radii[1] + L : max(radii[k-2]+radii[k-3]+2*L, radii[k-1] + radii[k-2] + L)));
}

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