Submission #1221253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221253		guilhermecpp	Race (IOI11_race)	C++17	100 / 100	281 ms	45244 KiB

race

#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define fi first
#define se second
//#define endl '\n'

typedef pair<int,int> pii;

const int N=200010;
const int K=1000010;

struct Node
{
    int c, d, q;
};

int n, k;
vector<pii> grafo[N];

int sub[N];
int pc[N];

vector<Node> values;

pii best[K][2];

int dfsCent(int u, int p)
{
    sub[u] = 1;
    for(auto [v,w] : grafo[u])
    {
        if(v==p || pc[v]) continue;
        sub[u] += dfsCent(v, u);
    }
    return sub[u];
}

int findCent(int u, int p, int q)
{
    for(auto [v,w] : grafo[u])
    {
        if(v==p || pc[v]) continue;
        if((2*sub[v])>q) return findCent(v, u, q);
    }
    return u;
}

int findCent(int u) 
{ 
    return findCent(u, u, dfsCent(u, u));
}

void dfsCalc(int u, int p, int wp, int d, int q, int c)
{
    d += wp;
    q++;
    if(k<d) return;
    values.pb({c,d,q});
    for(auto [v,w] : grafo[u])
    {
        if(v==p || pc[v]) continue;
        dfsCalc(v, u, w, d, q, c);
    }
    return;
}

void Change(int d, pii novo)
{
    for(int i = 0;i < 2;i++)
    {
        if(best[d][i].se!=novo.se) continue;
        best[d][i] = min(best[d][i], novo);
        if(best[d][0].fi>best[d][1].fi) swap(best[d][0], best[d][1]);
        return;
    }
    best[d][1] = min(best[d][1], novo);
    if(best[d][0].fi>best[d][1].fi) swap(best[d][0], best[d][1]);
    return;
}

int Calc(int u)
{
    int ans = N;
    int q = 0;
    for(auto [v,w] : grafo[u])
    {
        if(pc[v]) continue;
        q++;
        dfsCalc(v, u, w, 0, 0, v);
    }
    values.pb({u,0,0});
    for(auto [c,d,q] : values) Change(d,{q,c});
    for(auto [c,d,q] : values)
    {
        int nd = k-d;
        if(c!=best[nd][0].se)   ans = min(ans, best[nd][0].fi+q); 
        else                    ans = min(ans, best[nd][1].fi+q);
    }
    for(auto [c,d,q] : values) best[d][0] = best[d][1] = {N,-1};
    values.clear();
    return ans;
}

int Solv(int u, int p)
{
    int c = findCent(u);
    pc[c] = p;
    int ans = Calc(c);
    for(auto [v,w] : grafo[c])
    {
        if(pc[v]) continue;
        ans = min(ans, Solv(v, c));
    }
    return ans;
}

int best_path(int auxN, int auxK, int edges[][2], int len[])
{
    n = auxN;
    k = auxK;
    for(int i = 0;i < n-1;i++)
    {
        int u = edges[i][0]+1;
        int v = edges[i][1]+1;
        int w = len[i];
        grafo[u].pb({v,w});
        grafo[v].pb({u,w});
    }
    for(int i = 0;i <= k;i++) best[i][0] = best[i][1] = {N,-1};
    int ans = Solv(1, -1);
    if(ans==N) ans = -1;
    return ans;
}

// int32_t main()
// {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	cout.tie(0);

//     int n, k;
//     cin >> n >> k;

//     int h[n-1][2];
//     int l[n-1];
//     for(int i = 0;i < n-1;i++) cin >> h[i][0] >> h[i][1] >> l[i];

//     cout << best_path(n, k, h, l) << endl;

// 	return 0;
// }

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