Submission #17151

#	Time	Username	Problem	Language	Result	Execution time	Memory
17151		murat	Dreaming (IOI13_dreaming)	C++98	14 / 100	141 ms	35672 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++)
#define type(x) __typeof(x.begin())
#define pb push_back
#define mp make_pair
#define nd second
#define st first

const int N = 1e6 + 5;
const int inf = 1e9 + 5;

typedef pair< int , int > pii;

int n, m, x, y, z, val[N], h[N];
vector< pii > v[N];

pii dfs(int node, int root = 0) {
    pii tt = mp(0, node);
    foreach(it, v[node])
        if(it->st != root) {
            pii temp = dfs(it->st, node);
            temp.st += it->nd;
            tt = max(tt, temp);
        }
    return tt;
}

void dfs2(int node, int root = 0, int dist = 0) {
    val[node] = max(val[node], dist);
    foreach(it, v[node])
        if(it->st != root)
            dfs2(it->st, node, dist + it->nd);
}

int take(int node, int root = 0) {
    int nnn = node;
    h[node] = 1;
    foreach(it, v[node])
        if(it->st != root) {
            int ttt = take(it->st, node);
            if(val[ttt] < val[nnn])
                nnn = ttt;
        }
    return nnn;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    n = N;
    val[n] = inf * 2;

    for(int i = 0; i < M; i++) {
        int x = A[i], y = B[i], z = T[i];
        v[x].pb(mp(y, z));
        v[y].pb(mp(x, z));
    }

    priority_queue< pii, vector< pii > , greater< pii > > q;

    for(int i = 0; i < N; i++) {
        if(!h[i]) {
            int x = dfs(i).nd, y = dfs(x).nd;
            dfs2(x); dfs2(y);
            int nnn = take(i);
            q.push(mp(val[nnn], nnn));
        }
    }

    while(q.size() > 1) {
        pii t1 = q.top(); q.pop();
        pii t2 = q.top(); q.pop();
        int q1 = max(t1.st, t2.st + L);
        int q2 = max(t1.st + L, t2.st);
        v[t1.nd].pb(mp(t2.nd, L));
        v[t2.nd].pb(mp(t1.nd, L));
        pii tt;
        if(q1 < q2) q.push(tt =mp(q1, t1.nd));
        else q.push(tt = mp(q2, t2.nd));
    }


    int x = dfs(0).nd, ans = dfs(x).st;

    return ans;
}

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