제출 #1174409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174409		nrg_studio	Race (IOI11_race)	C++20	100 / 100	329 ms	101360 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 2e5;
vec<pii> adj[MAX_N];
map<ll,ll> dist[MAX_N];
ll weight[MAX_N] = {0}, unweight[MAX_N] = {0};
ll ans = INT_MAX;
int k2;

void dfs(int cur, int par) {
    dist[cur][0] = 0;

    for (auto[x,w] : adj[cur]) {
        if (x!=par) {
            dfs(x,cur);
            weight[x] += w;
            unweight[x]++;

            if (dist[x].size()>dist[cur].size()) {
                swap(dist[x],dist[cur]);
                swap(weight[x],weight[cur]);
                swap(unweight[x],unweight[cur]);
            }
            for (auto[x2,w2] : dist[x]) {
                ll x3 = k2-(x2+weight[x])-weight[cur], w3 = w2+unweight[x];
                if (dist[cur].count(x3)) {
                    chmin(ans,dist[cur][x3]+unweight[cur]+w3);
                }
            }
            for (auto[x2,w2] : dist[x]) {
                ll x3 = x2+weight[x]-weight[cur], w3 = w2+unweight[x]-unweight[cur];
                if (dist[cur].count(x3)) {
                    chmin(dist[cur][x3],w3);
                } else {
                    dist[cur][x3] = w3;
                }
            }
        }
    }

    //if (cur==1) {cout << weight[3] << '\n';cout << dist[cur].count(4-weight[cur])<<'\n';}
}

int best_path(int n, int k, int h[][2], int l[]) {
    k2 = k;
    for (int i=0;i<n-1;i++) {
        adj[h[i][0]].pb({h[i][1],l[i]});
        adj[h[i][1]].pb({h[i][0],l[i]});
    }
    dfs(0,0);
    return (ans==INT_MAX ? -1 : ans);
}

/*int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> n >> k;
    k2 = k;
    vec<int> ad(n-1), ad2(n-1);
    F0R(i,n-1) {
        cin >> ad[i] >> ad2[i];
    }
    F0R(i,n-1) {
        int a; cin >> a;
        adj[ad[i]].pb({ad2[i],a});
        adj[ad2[i]].pb({ad[i],a});
    }
    dfs(0,0);
    cout << (ans==INT_MAX ? -1 : ans) << '\n';
}*/

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