Submission #92009

#	Time	Username	Problem	Language	Result	Execution time	Memory
92009		easrui	Race (IOI11_race)	C++14	21 / 100	2724 ms	263168 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;

struct Edge{
    int x,d;
    Edge(){}
    Edge(int a, int b){
        x = a;
        d = b;
    }
};

vector<Edge> T[MN];
Edge A[MN][101];
Edge B[MN][101];

int DFS(int i, int val, int dis, int r, int K){
    if(dis==K) return val;
    if(dis>K) return MN;
    int res = MN;
    for(auto it : T[i]){
        //cout << i << ' ' << it.x << ' ' << r << '\n';
        if(it.x==r) continue;
        res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
    }
    return res;
}

int TDP(int i, int r, int K){
    int res = MN;
    for(auto it : T[i]){
        if(it.x==r) continue;
        res = min(res,TDP(it.x,i,K));
        for(int j=0; j<=K; j++){
            if(j+it.d<=K){
                int l = A[it.x][j].d+1;
                if(l<A[i][j+it.d].d){
                    B[i][j+it.d] = A[i][j+it.d];
                    A[i][j+it.d] = Edge(it.x,l);
                }
                else if(l<B[i][j+it.d].d) B[i][j+it.d] = Edge(it.x,l);
            }
        }
    }
    for(int k=0; k<=K; k++){
        if(A[i][k].x!=A[i][K-k].x) res = min(res,A[i][k].d+A[i][K-k].d);
        else res = min(res,B[i][k].d+A[i][K-k].d);
    }
    return res;
}

int best_path(int N, int K, int H[][2], int L[])
{
    int ans = MN;
    for(int i=0; i<N-1; i++){
        T[H[i][0]].push_back(Edge(H[i][1],L[i]));
        T[H[i][1]].push_back(Edge(H[i][0],L[i]));
    }
    for(int i=0; i<N; i++)
        for(int j=1; j<=K; j++){
            A[i][j].d = MN;
            B[i][j].d = MN;
        }
    if(K<=100){
        ans = TDP(0,0,K);
    }
    else{
        for(int i=0; i<N; i++){
            ans = min(ans,DFS(i,0,0,i,K));
        }
    }
    if(ans==MN) ans = -1;
    return ans;
}

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