제출 #573957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573957		nohaxjustsoflo	경주 (Race) (IOI11_race)	C++17	0 / 100	3 ms	4948 KiB

race

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen(-1e9, 1e8); ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 1e9+7;
const int mxlogN = 34;
const int mxK = 26;
//const ll inf = 1e18;
const int K = 100000;
struct edge
{
    int u,v,w;
    int other(int i)
    {
        return u^v^i;
    }
};
edge es[mxN];
bool vis[mxN];
int cc[mxN];
vector<int> adj[mxN];
void init(int i, int p=-1)
{
    cc[i]=1;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(p==j||vis[j]) continue;
        init(j,i);
        cc[i]+=cc[j];
    }
}
int find_centroid(int i, int n, int p=-1)
{
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(p==j||vis[j]) continue;
        if(cc[j]>n/2) return find_centroid(j,n,i);
    }
    return i;
}
const int inf=2e6;
int k;
map<int, int> mp;
int solve2(int i, int r, int w, bool edit, int d=1, int p=-1)
{
    if(w==k) return d;
    if(w>k) return inf;
    int ans=inf;
    if(!edit)
    {
        if(mp.count(k-w)) ans=min(ans, d+mp[k-w]);
    }
    else
    {
        if(mp.count(w)) mp[w]=min(mp[w], d);
        else mp[w]=d;
    }
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(p==j||vis[j]) continue;
        ans=min(ans,solve2(j,r,w+es[e].w,edit,d+1,i));
    }
    return ans;
}
int solve(int i)
{
    init(i);
    i=find_centroid(i,cc[i]);
    vis[i]=1;
    int ans=inf;
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(vis[j]) continue;
        ans=min(ans,solve2(j,j,es[e].w,0));
        solve2(j,j,es[e].w,1);
    }
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(vis[j]) continue;
        ans=min(ans,solve(j));
    }
    return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0; i+1<N; i++)
    {
        int u=H[i][0], v=H[i][1], w=L[i];
        es[i]={u,v,w};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    int ans=solve(0);
    if(ans==inf) ans=-1;
    return ans;
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k; cin >> n >> k;
    int H[n-1][2];
    for(int i=0; i+1<n; i++) cin >> H[i][0] >> H[i][1];
    int L[n-1];
    for(int i=0; i+1<n; i++) cin >> L[i];
    cout << best_path(n,k,H,L);
}*/

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