Submission #1182521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182521		burgerguy	Dreaming (IOI13_dreaming)	C++20	59 / 100	1096 ms	23332 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<ll>> neighbours;
    map<pair<ll,ll>,ll> edgeweight;
    vector<vector<ll>>().swap(neighbours);
    map<pair<ll,ll>,ll>().swap(edgeweight);
    for(int i=0;i<n;i++)
    {
        neighbours.push_back(vector<ll>());
    }
    ll x,y,z;
    for(int i=0;i<m;i++)
    {
        x=a[i];
        y=b[i];
        z=t[i];
        neighbours[x].push_back(y);
        neighbours[y].push_back(x);
        edgeweight[make_pair(min(x,y),max(x,y))]=z;
    }
    unordered_set<ll> seen;
    vector<ll> diameters({0,0});
    vector<ll> radii({0,0,0});
    for(int i=0;i<n;i++)
    {
        if(seen.find(i)==seen.end())
        {
            stack<ll> q;
            vector<ll> path(n,-1);
            vector<ll> weight(n,-1);
            unordered_set<ll> currseen;
            ll ep1,ep2,curr,total,currfurthest,currfurthestdistance;
            q.push(i);
            weight[i]=0;
            currfurthest=-1;
            currfurthestdistance=-1;
            while(!q.empty())
            {
                curr = q.top();
                q.pop();
                seen.insert(curr);
                for(auto neighbour:neighbours[curr])
                {
                    if(seen.find(neighbour)==seen.end())
                    {
                        weight[neighbour]=weight[curr]+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
                        q.push(neighbour);
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                if(weight[i]>currfurthestdistance)
                {
                    ep1=i;
                    currfurthestdistance=weight[i];
                }
            }
            ep2=ep1;
            currfurthestdistance=-1;
            total=0;
            vector<ll>(n,-1).swap(weight);
            weight[ep1]=0;
            unordered_set<ll>().swap(currseen);
            stack<ll>({ep1}).swap(q);
            while(!q.empty())
            {
                curr = q.top();
                q.pop();
                currseen.insert(curr);
                for(auto neighbour:neighbours[curr])
                {
                    if(currseen.find(neighbour)==currseen.end())
                    {
                        path[neighbour]=curr;
                        weight[neighbour]=weight[curr]+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
                        q.push(neighbour);
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                if(weight[i]>currfurthestdistance)
                {
                    ep2=i;
                    currfurthestdistance=weight[i];
                }
            }
            ll x,y,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];
            }
            radii.push_back(x);
            diameters.push_back(weight[ep2]);
        }
    }
    sort(diameters.begin(),diameters.end(),greater<long long>());
    sort(radii.begin(),radii.end(),greater<long long>());
    /*
    for(auto num:diameters)
    {
        cout << num << " ";
    }
    cout << endl;
    for(auto num:radii)
    {
        cout << num << " ";
    }
    cout << endl;
    */
    if(m==n-1)
    {
        return diameters[0];
    }
    if(m==n-2)
    {
        return max(radii[0]+radii[1]+l,diameters[0]);
    }
    else
    {
        return max(max(radii[0]+radii[1]+l,diameters[0]),radii[1]+radii[2]+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: 0 / 18
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23