Submission #479583

#	Time	Username	Problem	Language	Result	Execution time	Memory
479583		CyberSleeper	Race (IOI11_race)	C++14	0 / 100	10 ms	14412 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define pii     pair<int, int>
#define fi      first
#define se      second
#define pb      push_back

using namespace std;

const int MX=200007, INF=1e9+7;

vector<pii> adj[MX];
map<int, pii> ada[MX];
int N, K, ret=INF;

void add(int i, int j, int x){
    if(ada[i].count(j)){
        pii now=ada[i][j];
        if(now.se>x)
            now.se=x;
        if(now.fi>now.se)
            swap(now.fi, now.se);
        ada[i][j]=now;
    }else{
        ada[i][j]={x, INF};
    }
}
void calc(int x){
    ada[x][0]={0, 0};
    cout << endl;
    cout << x << endl;
    for(auto ii:ada[x]){
        int i=ii.fi, j=K-i;
        cout << "i: " << i << endl;
        if(i>=(K+1)/2)
            break;
        if(ada[x].count(i) && ada[x].count(j)){
            cout << i << ' ' << j << " good\n";
            ret=min(ret, ada[x][i].fi+ada[x][j].fi);
        }
    }
    if(K%2==0){
        int k=K/2;
        if(ada[x].count(k)){
            pii tmp=ada[x][k];
            if(tmp.se && tmp.se!=INF)
                ret=min(ret, tmp.fi+tmp.se);
        }
    }
}
void DFS(int par, int x){
    for(auto i:adj[x]){
        int v=i.fi, w=i.se;
        if(v==par)
            continue;
        DFS(x, v);
        if(w<=K)
            add(v, w, 1);
        if(ada[x].size()<ada[v].size())
            swap(ada[x], ada[v]);
        for(auto i:ada[v]){
            int tot=i.fi+w;
            pii cnt=i.se;
            if(tot>K)
                continue;
            add(x, tot, cnt.fi+1);
            add(x, tot, cnt.se+1);
        }
    }
    calc(x);
}

int best_path(int n, int k, int H[][2], int L[]){
    N=n, K=k;
    for(int i=0, u, v, w; i<N-1; i++){
        u=H[i][0], v=H[i][1], w=L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    DFS(0, 0);
    return (ret==INF?-1:ret);
}

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