Submission #1288883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288883		packmani	Dreaming (IOI13_dreaming)	C++20	0 / 100	48 ms	14308 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int NN = 1e5 + 5;
vector<pair<int,int>> adj[NN];
int maxnode;
ll maxdist, tmp, cur;
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;
        //cout << maxnode << ' ';
        maxdist=0;
        dfs2(maxnode,maxnode);
        //cout << maxnode << ' ';
        tmp = maxdist;
        cur=maxnode;
        //cout << tmp << '\n';
        while(from[cur]!=cur)
        {
            //cout << cur << ' ';
            tmp = min(tmp, max(maxdist-dist2[cur],dist2[cur]));
            cur=from[cur];
        }
        //cout << tmp << '\n';
        vec.push_back(tmp);
    }
    sort(vec.begin(), vec.end());
    /*
    for(int i=0;i<vec.size();i++)
    {
        cout << vec[i] << ' ' ;
    }
    cout << '\n';
    */
    if(vec[vec.size()-2]+L<vec[vec.size()-1]) return vec[vec.size()-1];
    return vec[vec.size()-1] + L + vec[vec.size()-2];
}

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