Submission #17160

#	Time	Username	Problem	Language	Result	Execution time	Memory
17160		murat	Dreaming (IOI13_dreaming)	C++14	100 / 100	209 ms	43704 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;

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

pii dfs(int node, int root = -1) {
    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;
}

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

static int take(int node, int root = -1) {
    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;

    for(int i = 0; i < N; i++)
        v[i].clear();

    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));
    }

    vector< pii > gg;
    gg.clear();

    memset(val, 0, sizeof val);
    memset(h, 0, sizeof h);

    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);
            gg.pb(mp(val[nnn], nnn));
        }
    }

    sort(gg.begin(), gg.end(), greater< pii >());

    for(int i = 1; i < gg.size(); i++) {
        v[gg[i].nd].pb(mp(gg[0].nd, L));
        v[gg[0].nd].pb(mp(gg[i].nd, L));
    }


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

    return ans;
}   

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < gg.size(); i++) {
                    ~~^~~~~~~~~~~
dreaming.cpp: At global scope:
dreaming.cpp:18:24: warning: 'z' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                        ^
dreaming.cpp:18:21: warning: 'y' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                     ^
dreaming.cpp:18:18: warning: 'x' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                  ^
dreaming.cpp:18:15: warning: 'm' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
               ^

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