Submission #572464

#	Time	Username	Problem	Language	Result	Execution time	Memory
572464		LunaMeme	Dreaming (IOI13_dreaming)	C++14	100 / 100	71 ms	17892 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXN = 1e5 + 5;
int visited[MAXN][2] = { 0 };
int dist[MAXN] = { 0 };
vii adj[MAXN];
int mx_dist = 0;
int mx_node[2];
int parent[MAXN];
void dfs(int curr,int par, int type){
    //cout << curr << ' ' << par << "   Type: " << type << '\n';
    if (visited[curr][type]) return;
    if (type == 1) parent[curr] = par;
    visited[curr][type] = 1;
    for (auto pr : adj[curr]){
        if (pr.first == par) continue;
        int next = pr.first;
        dist[next] = dist[curr] + pr.second;
        //cout << "FROM " << curr << " TO " << next << " : " << dist[next] << '\n';
        if (dist[next] >= mx_dist){
            mx_dist = dist[next];
            mx_node[type] = next;
        }
        dfs(next, curr, type);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    FOR(i, 0, N){
        adj[A[i]].PB(MP(B[i], T[i]));
        adj[B[i]].PB(MP(A[i], T[i]));
    }
    vi components;
    int inner_dist = 0;
    FOR(v, 0, N){
        if (visited[v][0]) continue;
        // new component
        mx_dist = 0;
        mx_node[0] = v;
        mx_node[1] = v;
        dfs(v, -1, 0);
        dist[mx_node[0]] = 0;
        mx_dist = 0;
        dfs(mx_node[0], -1, 1);
        //cout <<v << ' ' << mx_node[0] << ' ' << mx_node[1] << ' '<< mx_dist << '\n';
        inner_dist = max(inner_dist, mx_dist);
        int min_max = mx_dist;
        int node = mx_node[1];
        int centre = mx_node[1];
        while(node != -1){
            if (min_max >= max(dist[node], mx_dist - dist[node])){
                min_max = max(dist[node], mx_dist - dist[node]);
                centre  = node;
            }
            node = parent[node];
        }
        components.PB(min_max);
    }
    int temp;
    sort(components.rbegin(), components.rend());
    if (components.size() == 1){
        return inner_dist;
    }
    else if (components.size() == 2){
        temp = max(inner_dist, components[0] + L + components[1]);
        return temp;
    }
    else {
        temp = max(inner_dist, components[0] + L + components[1]);
        return max(temp, components[1] + 2*L + components[2]);
    }
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:56:13: warning: variable 'centre' set but not used [-Wunused-but-set-variable]
   56 |         int centre = mx_node[1];
      |             ^~~~~~

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