Submission #1182566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182566		Joon_Yorigami	Dreaming (IOI13_dreaming)	C++20	100 / 100	75 ms	9032 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    using pii = pair<ll, ll>;
    vector<vector<pair<ll,ll>>> neighbours(n,vector<pair<ll,ll>>());
    ll w,x,y,z;
    for(int i=0;i<m;i++)
    {
        x=a[i];
        y=b[i];
        z=t[i];
        neighbours[x].push_back(make_pair(y,z));
        neighbours[y].push_back(make_pair(x,z));
    }
    vector<bool> seen(n,false);
    vector<bool> currseen(n,false);
    vector<ll> temparr;
    vector<ll> path(n,-1);
    vector<ll> firstpassweight(n,-1);
    vector<ll> weight(n,-1);
    ll neighbour,edgeweight;
    ll d,r1,r2,r3;
    d=0;r1=0;r2=0;r3=0;
    for(int i=0;i<n;i++)
    {
        if(!seen[i])
        {
            stack<ll> q({i});
            ll ep1,ep2,curr,total,currfurthest,currfurthestdistance;
            firstpassweight[i]=0;
            currfurthestdistance=-1;
            ep1=i;
            while(!q.empty())
            {
                curr = q.top();
                q.pop();
                seen[curr]=true;
                for(auto &pa:neighbours[curr])
                {
                    neighbour=pa.first;
                    edgeweight=pa.second;
                    if(!seen[neighbour])
                    {
                        firstpassweight[neighbour]=firstpassweight[curr]+edgeweight;
                        if(firstpassweight[neighbour]>currfurthestdistance)
                        {
                            currfurthestdistance=firstpassweight[neighbour];
                            ep1=neighbour;
                        }
                        q.push(neighbour);
                    }
                }
            }
            ep2=ep1;
            currfurthestdistance=-1;
            total=0;
            weight[ep1]=0;
            stack<ll>({ep1}).swap(q);
            while(!q.empty())
            {
                curr = q.top();
                q.pop();
                currseen[curr]=true;
                for(auto &pa:neighbours[curr])
                {
                    neighbour=pa.first;
                    edgeweight=pa.second;
                    if(!currseen[neighbour])
                    {
                        path[neighbour]=curr;
                        weight[neighbour]=weight[curr]+edgeweight;
                        if(weight[neighbour]>currfurthestdistance)
                        {
                            currfurthestdistance=weight[neighbour];
                            ep2=neighbour;
                        }
                        q.push(neighbour);
                    }
                }
            }
            ll a,b;
            x=max(weight[ep1],weight[ep2]-weight[ep1]);
            y=min(weight[ep1],weight[ep2]-weight[ep1]);
            ll p1=ep2;
            while(p1!=ep1)
            {
                a=max(weight[p1],weight[ep2]-weight[p1]);
                b=min(weight[p1],weight[ep2]-weight[p1]);
                if(a<x)
                {
                    x=a;
                    y=b;
                }
                p1=path[p1];
            }
            vector<ll>({r1,r2,r3,x}).swap(temparr);
            sort(temparr.begin(),temparr.end());
            r1=temparr[3];
            r2=temparr[2];
            r3=temparr[1];
            d=max(d,weight[ep2]);
        }
    }
    if(m==n-1)
    {
        return d;
    }
    if(m==n-2)
    {
        return max(d,r1+r2+l);
    }
    else
    {
        return max(max(d,r1+r2+l),r2+r3+2*l);
    }
}
/*
int main()
{
    int n,m,l,k;
    cin >> n >> m >> l;
    int a[n];
    int b[n];
    int t[n];
    for(int i=0;i<n;i++)
    {
        cin >> k;
        a[i] = k;
        cin >> k;
        b[i] = k;
        cin >> k;
        t[i] = k;
    }
    //cout << "owo" << endl;
    cout << travelTime(n,m,l,a,b,t) << endl;
}
*/

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