Submission #1244041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244041		nguyenhuythach	경주 (Race) (IOI11_race)	C++20	0 / 100	3098 ms	99232 KiB

race

//luoi code qua chep tam code cu:)
#include<bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N = 1e6;
const int K = 1e6;
const int INF = 1e9;

int n, k, sz[N+10], bigc[N+10], st[N+10], fst[N+10], en[N+10], f[N+10], h[N+10], timer, res = INF;
vector<ii> adj[N+10];
map<int,int> mn;

void dfs(int u, int pu){
    sz[u]=1;
    st[u] = ++timer;
    fst[timer] = u;

    for (ii p: adj[u]){
        int v = p.fi;
        int w = p.se;
        if (v==pu) continue;
        f[v] = f[u]+w;
        h[v] = h[u]+1;
        if (f[v]==k) res = min(res, h[v]);
        dfs(v,u);
        sz[u]+=sz[v];

        if (sz[v]>sz[bigc[u]]) bigc[u]=v;
    }
    en[u] = timer;
}

void sackadd(int u){
    if (!mn[f[u]]) mn[f[u]]=INF;
    mn[f[u]] = min(mn[f[u]], h[u]);
}

void sacksub(int u){
    mn[f[u]] = INF;
}

void Sack(int u, int pu){
    for (ii p: adj[u]){
        int v = p.fi;
        if (v==pu || v==bigc[u]) continue;
        Sack(v,u);
        for (int i=st[v];i<=en[v];i++) sacksub(fst[i]);
    }

    if (bigc[u]) Sack(bigc[u], u);
    if (mn[f[u]+k]==0) mn[f[u]+k] = INF;
    res = min(res, mn[f[u]+k]-h[u]);

    sackadd(u);
    for (ii p: adj[u]){
        int v = p.fi;
        if (v==pu || v==bigc[u]) continue;
        for (int i=st[v];i<=en[v];i++){
            int c = k-(f[fst[i]]-f[u])+f[u];
            if (mn[c]==0) mn[c] =INF;
            if (c>=0) res = min(res, mn[c]+h[fst[i]]-2*h[u]);
        }
        for (int i=st[v];i<=en[v];i++) sackadd(fst[i]);
    }
}

void best_path(int n,int k,int h[][2],int l[])
{
	for(int i=0;i<=n-1;i++)
	{
		adj[h[i][0]+1].push_back({h[i][1]+1,l[i]});
		adj[h[i][1]+1].push_back({h[i][0]+1,l[i]});
	}
	dfs(1,0);
    Sack(1,0);
    cout <<(res>=2e5?-1:res);
}

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