제출 #60808

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
60808	2018-07-24 17:18:13	theknife2001	경주 (Race) (IOI11_race)	C++17	31 / 100	432 ms	133892 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+55;
vector < pair < int , int > > vec[M];
int k[M][105];
int b=1e9+55;
void dfs(int u , int p , int K)
{
    int v,c;
    int temp;
    for(auto x:vec[u])
    {
        v=x.first;
        c=x.second;
        if(v==p)
            continue ;
        dfs(v,u,K);
        for(int i=0;i<=K-c;i++)
            b=min(b,k[v][i]+k[u][K-i-c]+1);
        for(int i=0;i<=K-c;i++)
        {
            temp=k[v][i];
            k[u][i+c]=min(k[u][i+c],temp+1);
        }
    }
    b=min(b,k[u][K]);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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