Submission #126882

#	Time	Username	Problem	Language	Result	Execution time	Memory
126882		Bench0310	Dreaming (IOI13_dreaming)	C++17	100 / 100	139 ms	14432 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#pragma GCC optimize ("Ofast")

using namespace std;
const int N=100005;

vector<pair<int,int>> v[N];
vector<bool> vis(N,0);
vector<int> diameter(N,0);
vector<int> center(N,0);
vector<int> dist(N,-1);
vector<int> path;

pair<int,int> get_last(int a)
{
    vector<int> mod;
    dist[a]=0;
    queue<int> q;
    q.push(a);
    int last=a;
    while(!q.empty())
    {
        int e=q.front();
        q.pop();
        mod.push_back(e);
        vis[e]=1;
        for(pair<int,int> p:v[e])
        {
            int to=p.first;
            if(dist[to]!=-1) continue;
            dist[to]=dist[e]+p.second;
            q.push(to);
            if(dist[to]>dist[last]) last=to;
        }
    }
    pair<int,int> ret=make_pair(last,dist[last]);
    for(int i=0;i<(int)mod.size();i++) dist[mod[i]]=-1;
    return ret;
}

bool get_path(int a,int p,int b)
{
    if(a==b) return 1;
    for(pair<int,int> temp:v[a])
    {
        int to=temp.first;
        if(to==p) continue;
        if(get_path(to,a,b))
        {
            path.push_back(temp.second);
            return 1;
        }
    }
    return 0;
}

void get_center(int a,int id)
{
    int one,two,len;
    tie(one,ignore)=get_last(a);
    tie(two,len)=get_last(one);
    diameter[id]=len;
    path.clear();
    get_path(one,-1,two);
    int best=diameter[id];
    int sum=0;
    for(int i=0;i<(int)path.size();i++)
    {
        sum+=path[i];
        best=min(best,max(sum,diameter[id]-sum));
    }
    center[id]=best;
}

int solve(int n,int l)
{
    int id=0;
    for(int i=0;i<n;i++) if(vis[i]==0) get_center(i,id++);
    int res=0;
    vector<pair<int,int>> root;
    for(int i=0;i<id;i++)
    {
        res=max(res,diameter[i]);
        root.push_back(make_pair(center[i],i));
    }
    sort(root.begin(),root.end(),greater<pair<int,int>>());
    if(id>1) res=max(res,root[0].first+l+root[1].first);
    if(id>2) res=max(res,root[1].first+2*l+root[2].first);
    return res;
}

int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
    for(int i=0;i<m;i++)
    {
        v[a[i]].push_back(make_pair(b[i],t[i]));
        v[b[i]].push_back(make_pair(a[i],t[i]));
    }
    return solve(n,l);
}

/*int main()
{
    freopen("C:\\Users\\Benja\\Downloads\\ioi2013tests\\dreaming\\two-sticks-9.in","r",stdin);
    int n,m,l;
    scanf("%d%d%d",&n,&m,&l);
    for(int i=0;i<m;i++)
    {
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        v[a].push_back(make_pair(b,t));
        v[b].push_back(make_pair(a,t));
    }
    printf("%d\n",solve(n,l));
    return 0;
}*/

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