Submission #197496

#	Time	Username	Problem	Language	Result	Execution time	Memory
197496		handlename	Dreaming (IOI13_dreaming)	C++17	100 / 100	140 ms	18012 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > adjlist[100001]; //node,weight
int treenum[100001];
vector<pair<int,int> > nodesused; //node,weight
vector<int> tree;
bool visited[100001];
pair<int,int> dfs(int pos){ //furthest node,distance
    if (visited[pos]) return make_pair(pos,-1e9);
    tree.push_back(pos);
    visited[pos]=true;
    int node=pos,maxi=0;
    for (auto i:adjlist[pos]){
        pair<int,int> temp=dfs(i.first);
        if (maxi<temp.second+i.second){
            maxi=temp.second+i.second;
            node=temp.first;
        }
    }
    nodesused.push_back(make_pair(node,maxi));
    //cout<<pos<<" "<<node<<" "<<maxi<<'\n';
    return make_pair(node,maxi);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0;i<M;i++){
        adjlist[A[i]].push_back(make_pair(B[i],T[i]));
        adjlist[B[i]].push_back(make_pair(A[i],T[i]));
    }
    vector<int> radiuses;
    int maxsofar=0;
    for (int i=0;i<N;i++){
        if (!visited[i]){
            //cout<<i<<'\n';
            pair<int,int> temp=dfs(i);
            nodesused.clear();
            for (auto nod:tree){
                visited[nod]=false;
            }
            tree.clear();
            pair<int,int> temptwo=dfs(temp.first);
            tree.clear();
            int mini=temptwo.second;
            if (M==N-1) return mini;
            maxsofar=max(maxsofar,mini);
            for (auto p:nodesused){
                //cout<<p.first<<" "<<p.second<<" "<<temptwo.second<<'\n';
                mini=min(mini,max(p.second,temptwo.second-p.second));
            }
            //cout<<mini<<'\n';
            radiuses.push_back(mini);
        }
    }
    sort(radiuses.begin(),radiuses.end());
    int nn=radiuses.size();
    maxsofar=max(maxsofar,radiuses[nn-2]+radiuses[nn-1]+L);
    if (nn>=3) maxsofar=max(maxsofar,radiuses[nn-2]+radiuses[nn-3]+L*2);
    return maxsofar;
}

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