Submission #463479

#	Time	Username	Problem	Language	Result	Execution time	Memory
463479		mshandilya	Dreaming (IOI13_dreaming)	C++14	0 / 100	611 ms	14688 KiB

dreaming

#include "bits/stdc++.h"
#include "dreaming.h"
#define adj_list vector<list<pair<int, int>>>
#define viii vector<pair<int, pair<int, int>>>
#define vi vector<int>
using namespace std;

adj_list adj;
viii max_sub_dist, smax_sub_dist;
vi trees;

void dfs1(int root) {
    max_sub_dist[root].first = 0;
    for(auto& i : adj[root]) {
        if(max_sub_dist[i.first].first==-1) {
            dfs1(i.first);
            if(i.second + max_sub_dist[i.first].first > max_sub_dist[root].first) {
                smax_sub_dist[root] = max_sub_dist[root];
                max_sub_dist[root].first = i.second + max_sub_dist[i.first].first;
                max_sub_dist[root].second = i;
            }
        }
    }
}

int dfs2(int root) {
    int mchild = max_sub_dist[root].second.first; //the index of the maximum child
    int mdist = max_sub_dist[root].first; //the maximum distance from root
    int sdist = smax_sub_dist[root].first; //the second to maximum distance from root
    int mpcdist = max_sub_dist[root].second.second; //the distance to maximum child
    int mcdist = max_sub_dist[mchild].first; //the maximum distance from maximum child
    int scdist = smax_sub_dist[mchild].first; // the second to maximum distance from maximum child
    if(mdist > mpcdist + sdist) {
        if(mcdist < mpcdist + sdist) {
            max_sub_dist[mchild].first = mpcdist + sdist;
            smax_sub_dist[mchild].first = mcdist;
            return mchild;
        }
        if(mpcdist + sdist < scdist)
            return dfs2(mchild);
        smax_sub_dist[mchild].first = sdist + mpcdist;
        return dfs2(mchild);
    }
    else
        return root;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.assign(N, list<pair<int, int>> ());
    for(int i = 0; i<M; i++) {
        adj[A[i]].push_back(make_pair(B[i], T[i]));
        adj[B[i]].push_back(make_pair(A[i], T[i]));
    }
    max_sub_dist.assign(N, make_pair(-1, make_pair(-1, 0)));
    smax_sub_dist.assign(N, make_pair(0, make_pair(-1, 0)));
    int mdist = 0, sdist = 0;
    for(int i = 0, node; i<N; i++) {
        if(max_sub_dist[i].first==-1) {
            dfs1(i);
            node = dfs2(i);
            if(max_sub_dist[node].first>mdist) {
                mdist = max_sub_dist[node].first;
                sdist = smax_sub_dist[node].first;
            }
            trees.push_back(max_sub_dist[node].first);
        }
    }
    sort(trees.begin(),  trees.end(), std::greater_equal<int> ());
    for(int i = 1, s = trees.size(); i<s; i++) {
        if(trees[i-1] > trees[i] + L) {
            trees[i] = trees[i-1];
            sdist = max(trees[i] + L, sdist);
        }
        else {
            trees[i] = trees[i] + L;
            sdist = mdist;
            mdist = trees[i] + L;
        }
    }
    return mdist+sdist;
}

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