oj.uz

Submission #63115

# Submission time Handle Problem Language Result Execution time Memory
63115 2018-07-31T19:44:43 Z FLDutchman Race (IOI11_race) C++14
0 / 100
 4 ms 772 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define V vector

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

struct edge {int v, l;};

int N, K;
V<V<edge>> adj;
V<bool> used;

int centroid(int u, int par, int &root, int size){
    //cout << "centroid " << u << " " << par << " " << size << endl;
    int sz = 1;
    int ma = 0;
    for(edge e : adj[u]) if(!used[e.v] and e.v != par) {
        int s = centroid(e.v, u, root, size);
        sz += s;
        ma = max(ma, s);
    }
    if(max(ma, size-sz) <= size/2) root = u;
    return sz;
}

void dfs(int u, int par, int d, int l, vii &paths){
    //cout << "dfs " << u << " " << par << endl;
    paths.pb({d, l});
    for(edge e : adj[u]) if(!used[e.v] and e.v != par) dfs(e.v, u, d+e.l, l+1, paths);
}

int shortest(int u){
    //cerr << "shortest " << u << endl;
    int root, sz;
    sz = centroid(u, u, root, 0);
    centroid(u, u, root, sz);
    //cout << "root " << root << endl;
    used[root] = 1;
    map<int, int> paths;
    int best = 1e9;
    for(edge e : adj[root]) if(!used[e.v]) {
        vii pa;
        dfs(e.v, root, e.l, 1, pa);
        for(ii p : pa){
            int &l = paths[ K - p.fst ];
            if(l != 0) best = min(best, p.snd + l);
        }
        for(ii p : pa){
            int &l = paths[p.fst];
            if(l == 0) l = p.snd;
            else l = min(l, p.snd);
        }
    }
    for(edge e : adj[root]) if(!used[e.v]) best = min(best, shortest(e.v));
    return best;
}

INT best_path(INT n, INT k, INT H[][2], INT L[]) {
    N = n; K = k;
    adj.resize(N);
    used.assign(N, 0);
    FOR(i, 0, N) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    int res = shortest(0);
    return res == 1e9 ? -1 : res;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 3 ms 772 KB Output is correct
8 Incorrect 4 ms 772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 3 ms 772 KB Output is correct
8 Incorrect 4 ms 772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 3 ms 772 KB Output is correct
8 Incorrect 4 ms 772 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 3 ms 772 KB Output is correct
8 Incorrect 4 ms 772 KB Output isn't correct
9 Halted 0 ms 0 KB -