Submission #404915

#	Time	Username	Problem	Language	Result	Execution time	Memory
404915		Theo830	Dreaming (IOI13_dreaming)	C++17	18 / 100	60 ms	11736 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
ll INF = INT_MAX;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "dreaming.h"
int res = 0;
vector<ll>dist[2];
ll subtree[100005];
ll pos = 0;
vector<vector<ii> >adj;
ll maxi = 0;
ll node;
bool v[100005] = {0};
priority_queue<ii,vector<ii>,greater<ii> > pq;
void dfs(ll s,ll p,ll sum){
    maxi = max(maxi,sum);
    v[s] = 1;
    subtree[s] = pos;
    if(sum == maxi){
        node = s;
    }
    for(auto x:adj[s]){
        if(x.F != p){
            dfs(x.F,s,sum+x.S);
        }
    }
}
void dijkstra(ll s,ll pos){
    dist[pos][s] = 0;
    pq.push(ii(0,s));
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w,u;
        w = f.F;
        u = f.S;
        if(w > dist[pos][u]){
            continue;
        }
        for(auto x:adj[u]){
            if(dist[pos][u] + 1 < dist[pos][x.F]){
                dist[pos][x.F] = dist[pos][u] + x.S;
                pq.push(ii(dist[pos][x.F],x.F));
            }
        }
    }
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    adj.assign(n+5,vector<ii>());
    f(i,0,m){
        adj[A[i]].pb(ii(B[i],T[i]));
        adj[B[i]].pb(ii(A[i],T[i]));
    }
    dist[0].assign(n+5,INF);
    dist[1].assign(n+5,INF);
    f(i,1,n+1){
        if(v[i] == 0){
            maxi = 0;
            dfs(i,0,0);
            ll u = node;
            maxi = 0;
            dfs(u,0,0);
            dijkstra(u,0);
            dijkstra(node,1);
            pos++;
        }
    }
    ll mini[pos];
    f(i,0,pos){
        mini[i] = 1e9+7;
    }
    f(i,1,n+1){
        res = max({res,dist[0][i],dist[1][i]});
        mini[subtree[i]] = min(mini[subtree[i]],max(dist[0][i],dist[1][i]));
    }
    sort(mini,mini+pos);
    if(pos >= 2){
        res = max(res,mini[pos-1] + mini[pos-2] + L);
    }
    if(pos >= 3){
        res = max(res,mini[pos-3] + mini[pos-2] + 2 * L);
    }
    return res;
}

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