Submission #480936

#	Time	Username	Problem	Language	Result	Execution time	Memory
480936		peti1234	Race (IOI11_race)	C++17	100 / 100	543 ms	101804 KiB

race

#include <bits/stdc++.h>

using namespace std;
const int c=200005;
int szint[c], ki[c];
long long dist[c], cel, ans=c;
map<long long, long long> m[c];
vector<pair<int, int> > sz[c];
bool v[c];

void unio(int a, int b) {
    //cout << "unio " << a << " " << b << "\n";
    int aa=ki[a], bb=ki[b], sa=m[aa].size(), sb=m[bb].size();
    //cout << "si " << sa << " " << sb << "\n";
    long long ert=cel+2*dist[a];
    if (sa>=sb) {
        for (auto p:m[bb]) {
            long long fi=p.first, se=p.second, inv=ert-fi;
            if (m[aa].find(inv)!=m[aa].end()) {
                ans=min(ans, se+m[aa][inv]-2*szint[a]);
            }
        }
        for (auto p:m[bb]) {
            long long fi=p.first, se=p.second;
            if (m[aa].find(fi)!=m[aa].end()) {
                m[aa][fi]=min(m[aa][fi], se);
            } else {
                m[aa][fi]=se;
            }
        }
    } else {
        ki[a]=bb;
        for (auto p:m[aa]) {
            long long fi=p.first, se=p.second, inv=ert-fi;
            if (m[bb].find(inv)!=m[bb].end()) {
                ans=min(ans, se+m[bb][inv]-2*szint[a]);
            }
        }
        for (auto p:m[aa]) {
            long long fi=p.first, se=p.second;
            if (m[bb].find(fi)!=m[bb].end()) {
                m[bb][fi]=min(m[bb][fi], se);
            } else {
                m[bb][fi]=se;
            }
        }
    }
}

void dfs(int a) {
    v[a]=true;
    ki[a]=a;
    m[a][dist[a]]=szint[a];
    for (auto p:sz[a]) {
        int x=p.first, y=p.second;
        if (!v[x]) {
            szint[x]=szint[a]+1;
            dist[x]=dist[a]+y;
            dfs(x);
            unio(a, x);
        }
    }
}

int best_path(int n, int K, int H[][2], int L[]) {
    cel=K;
    for (int i=0; i<n-1; i++) {
        int a=H[i][0], b=H[i][1], c=L[i];
        a++, b++;
        sz[a].push_back({b, c});
        sz[b].push_back({a, c});
    }
    szint[1]=1;
    dfs(1);
    return (ans==c ? -1 : ans);
}
/*
int main()
{
    int n, k;
    cin >> n >> k;
    int H[n-1][2], 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) << "\n";
    return 0;
}
*/
/*
5 4
0 1 1
1 2 1
2 3 1
3 4 1
*/

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