Submission #764136

#	Time	Username	Problem	Language	Result	Execution time	Memory
764136		fatemetmhr	Dreaming (IOI13_dreaming)	C++17	100 / 100	55 ms	17292 KiB

dreaming

//  ~ Be Name Khoda ~  //

#include "dreaming.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

vector <pair<int, int>> adj[maxn5];
vector <int> ver, av;
int par[maxn5], h[maxn5], edpar[maxn5];
bool mark[maxn5];

void dfs1(int v){
    mark[v] = true;
    av.pb(v);
    for(auto [u, w] : adj[v]) if(!mark[u]){
        h[u] = h[v] + w;
        dfs1(u);
    }
}

void dfs2(int v){
    mark[v] = true;
    for(auto [u, w] : adj[v]) if(!mark[u]){
        h[u] = h[v] + w;
        par[u] = v;
        edpar[u] = w;
        dfs2(u);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i = 0; i < m; i++){
        adj[a[i]].pb({b[i], t[i]});
        adj[b[i]].pb({a[i], t[i]});
    }
    int ans = 0;

    for(int i = 0; i < n; i++) if(!mark[i]){
        av.clear();
        h[i] = 0;
        dfs1(i);
        if(av.size() == 1){
            ver.pb(0);
            continue;
        }
        int dim1 = i;
        for(auto u : av){
            mark[u] = false;
            if(h[u] >= h[dim1])
                dim1 = u;
        }
        h[dim1] = 0;
        par[dim1] = -1;
        edpar[dim1] = 0;
        dfs2(dim1);
        int dim2 = i;
        for(auto u : av) if(h[u] >= h[dim2])
            dim2 = u;
        ans = max(ans, h[dim2]);
        int x = h[dim2], y = 0, v = dim2;
        while(par[v] != -1){
            int u = par[v];
            if(x - edpar[v] >= y + edpar[v]){
                x -= edpar[v];
                y += edpar[v];
                v = u;
            }
            else
                break;
        }
        int u = par[v];
        int x2 = x - edpar[v], y2 = y + edpar[v];
        ver.pb(min(max(x2, y2), max(x, y)));
        //cout << "having one " << dim1 << ' ' << dim2 << ' ' << v << ' ' << u << ' ' << x << ' ' << y << ' ' << x2 << ' ' << y2 << endl;
    }
    if(ver.size() == 1)
        return ans;
    if(ver.size() == 2){
        ans = max(ans, ver[0] + ver[1] + l);
        return ans;
    }
    sort(all(ver));
    int x = ver.back(), y = ver[int(ver.size()) - 2], z = ver[int(ver.size()) - 3];
    return max({ans, x + l + y, 2 * l + y + z});
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:90:13: warning: unused variable 'u' [-Wunused-variable]
   90 |         int u = par[v];
      |             ^

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