Submission #1853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1853		tncks0121	Dreaming (IOI13_dreaming)	C++98	100 / 100	136 ms	14496 KiB

dreaming

#include "dreaming.h"

#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <memory.h>
#include <assert.h>

using namespace std;

const int N_ = 200005;
const int C = 10005;
const int inf = 1987654321;

struct Edge {
    int v, c;
    Edge(): v(0), c(0) { }
    Edge(int v, int c): v(v), c(c) { }
};

struct Root {
    int v, c;    
    Root(): v(0), c(0) { }
    Root(int v, int c): v(v), c(c) { }
    bool operator< (const Root &t) const { return c < t.c; }
};

int N, M, L;
vector<Edge> Gph[N_];

int farch[N_][2], farthest[N_];
int Que[N_], Par[N_], Cst[N_], Qf, Qr;
bool visited[N_];
priority_queue<Root> H;
int res;

void findRoot (int r) {
    Qf = Qr = 0; Que[++Qr] = r;
    visited[r] = 1;
    while(Qf < Qr) {
        int u = Que[++Qf]; //printf("%d(%d) ", u, Par[u]);
        for(int i = 0; i < Gph[u].size(); i++) {
            Edge &e = Gph[u][i];
            if(!visited[e.v]) {
                visited[e.v] = 1;
                Par[e.v] = u; Cst[e.v] = e.c; 
                Que[++Qr] = e.v;
            }
        }
    }
    //puts("");
    
    for(int i = Qr; i > 0; i--) {
        int u = Que[i], p = Par[u], c = Cst[u] + farch[u][0];
        //printf("%d: %d %d\n", u, farch[u][0], farch[u][1]);
        if(farch[p][0] < c) {
            farch[p][1] = farch[p][0];
            farch[p][0] = c;
        }else if(farch[p][1] < c){
            farch[p][1] = c;
        }
    }
    
    Qf = Qr = 0; Que[++Qr] = r;
    while(Qf < Qr) {
        int u = Que[++Qf];
        for(int i = 0; i < Gph[u].size(); i++) {
            Edge &e = Gph[u][i];
            if(Par[e.v] != u) continue;
            Que[++Qr] = e.v;
            
            int w = (e.c + farch[e.v][0] >= farch[u][0]);
            farthest[e.v] = e.c + max(farthest[u], farch[u][w]);
        }
    }
    
    int root = r;
    for(int i = 1; i <= Qr; i++) {
        int u = Que[i];
        farthest[u] = max(farthest[u], farch[u][0]);
        res = max(res, farthest[u]);
        res = max(res, farch[u][0] + farch[u][1]);
        if(farthest[u] < farthest[root]) root = u;
    }
    
    H.push(Root(root, farthest[root]));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int i, j;
    
    ::N = N; ::M = M; ::L = L;
    for(i = 0; i < M; i++) {
        int u = A[i]+1, v = B[i]+1;
        Gph[u].push_back(Edge(v, T[i]));
        Gph[v].push_back(Edge(u, T[i]));
    }
    
    for(i = 1; i <= N; i++) {
        if(!visited[i]) findRoot(i);
    }
    
    while(H.size() > 1) {
        Root r2 = H.top(); H.pop();
        Root r1 = H.top(); H.pop();
        res = max(res, r1.c + L + r2.c);
        Gph[r1.v].push_back( Edge(r2.v, L) );
        Gph[r2.v].push_back( Edge(r1.v, L) );
        H.push( Root(r2.v, max(r1.c + L, r2.c)) );
    }
    
    memset(visited, 0, sizeof visited);
    memset(farch, 0, sizeof farch);
    memset(farthest, 0, sizeof farthest);
    memset(Cst, 0, sizeof Cst);
    
    findRoot(1);
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void findRoot(int)':
dreaming.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < Gph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
dreaming.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < Gph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:91:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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