Submission #1178496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178496		Joon_Yorigami	Dreaming (IOI13_dreaming)	C++20	0 / 100	1092 ms	24280 KiB

dreaming

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

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+1;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;
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    vector<long long> distance;
    vector<long long> path;
    unordered_set<ll> seen;
    unordered_set<ll> currseen;
    unordered_set<ll>().swap(seen);
    ll ep1,ep2;
    x=0;y=0;
    for(int startingnode=0;startingnode<n;startingnode++)
    {
        if(seen.find(startingnode)!=seen.end())
        {
            continue;
        }
        unordered_set<ll>().swap(currseen);
        //currseen.insert(startingnode);
        vector<ll>(n,-1).swap(distance);
        vector<ll>(n,-1).swap(path);
        distance[startingnode]=0;
        priority_queue<pii, vector<pii>, greater<pii>>().swap(q);
        q.push(make_pair(0,startingnode));
        ll curr,weight,furthest;
        furthest=startingnode;
        while(!q.empty())
        {
            weight=q.top().first;
            curr=q.top().second;
            q.pop();
            seen.insert(curr);
            if(currseen.find(curr)!=currseen.end())
            {
                continue;
            }
            furthest=curr;
            currseen.insert(curr);
            for(auto neighbour:neighbours[curr])
            {
                if(currseen.find(neighbour)!=currseen.end())
                {
                    continue;
                }
                ll val;
                val=weight+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
                if(distance[neighbour]==-1 || val<distance[neighbour])
                {
                    //path[neighbour]=curr;
                    distance[neighbour]=val;
                    q.push(make_pair(val,neighbour));
                }
            }
        }
        ep1=furthest;


        unordered_set<ll>().swap(currseen);
        //currseen.insert(startingnode);
        vector<ll>(n,-1).swap(distance);
        vector<ll>(n,-1).swap(path);
        distance[ep1]=0;
        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>().swap(q);
        q.push(make_pair(0,ep1));
        furthest=ep1;
        while(!q.empty())
        {
            weight=q.top().first;
            curr=q.top().second;
            q.pop();
            if(currseen.find(curr)!=currseen.end())
            {
                continue;
            }
            furthest=curr;
            currseen.insert(curr);
            for(auto neighbour:neighbours[curr])
            {
                if(currseen.find(neighbour)!=currseen.end())
                {
                    continue;
                }
                ll val;
                val=weight+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
                if(distance[neighbour]==-1 || val<distance[neighbour])
                {
                    distance[neighbour]=val;
                    path[neighbour]=curr;
                    q.push(make_pair(val,neighbour));
                }
            }
        }
        ep2=furthest;
        path[ep1]=ep1;
        ll total,p1,x1,y1,best1,best2;
        total=distance[ep2];
        vector<ll> temparr;
        x1=distance[ep2];
        y1=0;
        best1=x1;
        best2=y1;
        p1=ep2;
        while(p1!=ep1)
        {
            ll val;
            val=edgeweight[make_pair(min(p1,path[p1]),max(p1,path[p1]))];
            x1-=val;
            y1+=val;
            if(max(x1,y1)<max(best1,best2))
            {
                best1=max(x1,y1);
                best2=min(x1,y1);
            }
            p1=path[p1];
            //cout << best1 << " " << best2 << endl;
        }
        vector<ll>({x,y,best1,best2}).swap(temparr);
        //cout << "endpoints: "<< ep1 << " " << ep2 << endl;
        sort(temparr.begin(),temparr.end());
        x=temparr[3];
        y=temparr[2];
    }
    //cout << x << " " << y << endl;
    return x+y+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: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23