Submission #1288888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288888		packmani	Dreaming (IOI13_dreaming)	C++20	47 / 100	50 ms	17632 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int NN = 1e6 + 5;
vector<pair<int,ll>> adj[NN];
int maxnode;
ll maxdist, tmp, cur, maxxdist;
ll dist[NN],dist2[NN];
int vis[NN],from[NN];
vector<ll> vec;
void dfs(int node, int par)
{
    maxdist = max(maxdist, dist[node]);
    if(maxdist==dist[node]) maxnode=node;
    for(auto to:adj[node])
    {
        if(to.first==par) continue;
        vis[to.first]=1;
        dist[to.first]=dist[node]+to.second;
        dfs(to.first, node);
    }
}
void dfs2(int node, int par)
{
    maxdist = max(maxdist, dist2[node]);
    if(maxdist==dist2[node]) maxnode=node;
    for(auto to:adj[node])
    {
        if(to.first==par) continue;
        from[to.first]=node;
        dist2[to.first]=dist2[node]+to.second;
        dfs2(to.first, node);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++)
    {
        adj[A[i]].push_back({B[i],T[i]});
        adj[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<N;i++)
    {
        if(vis[i]) continue;
        maxdist=0;
        dist[i]=0;
        vis[i]=1;
        dfs(i,i);
        from[maxnode]=maxnode;
        dist2[maxnode]=0;
        maxdist=0;
        dfs2(maxnode,maxnode);
        maxxdist = max(maxxdist, maxdist);
        tmp = maxdist;
        cur = maxnode;
        while(from[cur]!=cur)
        {
            tmp = min(tmp, max(maxdist-dist2[cur],dist2[cur]));
            cur=from[cur];
        }
        vec.push_back(tmp);
    }
    sort(vec.begin(), vec.end());
    cur = vec[0];
    for(int i=1;i<vec.size()-1;i++)
    {
        cur = max(min(cur,vec[i])+L, max(cur,vec[i]));
    }
    return max(maxxdist, cur + 1ll*L + vec[vec.size()-1]);
    //if(vec[vec.size()-2]+L<vec[vec.size()-1])return max(maxxdist, vec[vec.size()-1] + 1ll*L + vec[vec.size()-2]);

}

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