Submission #342884

#	Time	Username	Problem	Language	Result	Execution time	Memory
342884		blue	Harbingers (CEOI09_harbingers)	C++11	20 / 100	1096 ms	20588 KiB

harbingers

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
 
int N;
vector<int>* e; //temp arrays
vector<int>* dist;
int* P; //parent of town i if tree is rooted at 1
int* D; //distance between i and P[i]
int* S; //starting duration for ith harbinger
int* V; //min/km speed for ith harbinger
int* res;
 
void build(int u)
{
    for(unsigned int i = 0; i < e[u].size(); i++)
    {
        if(e[u][i] == P[u]) continue;
        P[e[u][i]] = u;
        D[e[u][i]] = dist[u][i];
        build(e[u][i]);
    }
}
 
void compute(int u)
{
    int t = S[u] + D[u]*V[u];
    res[u] = 2000000000;
    for(int i = P[u]; i != 0; i = P[i])
    {
        res[u] = min(res[u], t + res[i]);
        t += D[i]*V[u];
    }
    for(int v: e[u]) if(v != P[u])
    {
        compute(v);
    }
}
 
int main()
{
    //ifstream fin("harbingers.in");
    //ofstream fout("harbingers.out");
    cin >> N;
 
    e = new vector<int>[N+1];
    dist = new vector<int>[N+1];
 
    P = new int[N+1];
    D = new int[N+1];
    int u, v, d;
    for(int i = 1; i < N; i++)
    {
        cin >> u >> v >> d;
        e[u].push_back(v);
        e[v].push_back(u);
        dist[u].push_back(d);
        dist[v].push_back(d);
    }
    P[1] = 0;
    D[1] = 0;
    build(1);
 
    S = new int[N+1];
    V = new int[N+1]; //MINUTES PER KM, NOT KM PER MIN
    for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];
 
    S[1] = 0;
    V[1] = 0;
 
    res = new int[N+1];
    res[1] = 0;
 
    for(int i: e[1]) compute(i);
 
    for(int i = 2; i <= N; i++) cout << res[i] << '\n';
    return 0;
}

• Subtask 1: 20 / 100