Submission #348758

#	Time	Username	Problem	Language	Result	Execution time	Memory
348758		soroush	Race (IOI11_race)	C++14	21 / 100	3036 ms	38964 KiB

race

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "race.h"
 
using namespace std;
 
typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
 
const int N = 2e5 + 10;
int S[N], M[N], n, k, ret = 1e9; vector<pii> adj[N]; unordered_map<int, int> mp;
 
void preDFS(int v, int p = -1) {
    S[v] = 1;
    for (pii u : adj[v]) {
        if (u.F != p && !M[u.F]) preDFS(u.F, v), S[v] += S[u.F];
    }
}
 
int centroid(int v, int s, int p = -1) {
    for (pii u : adj[v]) {
        if (!M[u.F] && u.F != p && 2 * S[u.F] > s) return centroid(u.F, s, v);
    }
    return v;
}
 
void add(int v, int iw, int p, int h = 1) {
   if (mp.count(iw)) mp[iw] = min(mp[iw], h);
   else mp[iw] = h;
   for (pii u : adj[v]) {
       if (!M[u.F] && u.F != p) add(u.F, iw + u.S, v, h + 1);
   }
}
 
void calc(int v, int iw, int p, int h = 1) {
    if (iw > k) return;
    if (iw == k) ret = min(ret, h);
    else if (mp.count(k - iw)) ret = min(ret, h + mp[k - iw]);
    for (pii u : adj[v]) {
        if (!M[u.F] && u.F != p) calc(u.F, iw + u.S, v, h + 1);
    }
}
 
void solve(int v) {
    for (pii u : adj[v]) {
      	if (M[u.F]) continue;
        calc(u.F, u.S, v);
        add(u.F, u.S, v);
    }
}
 
void decompose(int v) {
    preDFS(v);
    v = centroid(v, S[v]);
    // solve
    solve(v);
    mp = {};
    M[v] = 1;
    for (pii u : adj[v]) if (!M[u.F]) decompose(u.F);
}
 
int best_path(int _n, int _k, int h[][2], int l[]) {
    n = _n, k = _k;
    for (int i = 0; i < n - 1; i++) {
        int u = h[i][0] + 1, v = h[i][1] + 1;
        adj[u].push_back({v, l[i]});
        adj[v].push_back({u, l[i]});
    }
    decompose(1);
    return ret == 1e9 ? -1 : ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57