Submission #1316107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316107		khanhphucscratch	Dreaming (IOI13_dreaming)	C++20	100 / 100	44 ms	15032 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<array<int, 2>> ad[100005];
int dis[100005], curmin = 0, curmax = 0;
bool visited[100005];
void dfs(int u)
{
    visited[u] = 1; dis[u] = 0;
    for(auto &[v, d] : ad[u]) if(visited[v] == 0){
        dfs(v); dis[u] = max(dis[u], dis[v] + d);
    }
    visited[u] = 0;
}
void reroot(int u)
{
    visited[u] = 1;
    pair<int, int> bestval = {0, 0};
    for(auto &[v, d] : ad[u]){
        if(bestval.second < dis[v]+d) bestval.second = dis[v]+d;
        if(bestval.first < bestval.second) swap(bestval.first, bestval.second);
    }
    dis[u] = bestval.first;
    //cerr<<"A"<<u<<" "<<dis[u]<<endl;
    curmin = min(curmin, dis[u]); curmax = max(curmax, bestval.first + bestval.second);
    for(auto &[v, d] : ad[u]) if(visited[v] == 0){
        int re = dis[u];
        if(dis[v] + d == bestval.first) dis[u] = bestval.second;
        reroot(v);
        dis[u] = re;
    }
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    for(int i = 0; i < m; i++){
        int u = A[i], v = B[i], d = T[i];
        ad[u].push_back({v, d});
        ad[v].push_back({u, d});
    }
    vector<int> a;
    for(int i = 0; i < n; i++) if(visited[i] == 0){
        curmin = 1e18; dfs(i);
        reroot(i);
        a.push_back(curmin);
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = 0;
    if(a.size() >= 2) ans = max(ans, a[0] + a[1] + l);
    if(a.size() >= 3) ans = max(ans, a[1] + a[2] + 2*l);
    return max(ans, curmax);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:41:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   41 |         curmin = 1e18; dfs(i);
      |                  ^~~~

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