제출 #543173

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
543173	2022-03-29 15:43:04	__Variatto	경주 (Race) (IOI11_race)	C++17	100 / 100	666 ms	59448 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 <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, MAXV=1e6+10;
vector<pair<int,int>>g[MAXV];
int n, k, centr, podd[MAXV], o[MAXV];
int odw[MAXV], wynik=MAXV, mini[MAXV];
void dfs(int v, int oj, int roz){
    podd[v]=1, o[v]=oj;
    int maxi=0;
    for(auto s:g[v]){
        if(s.fi!=oj && !odw[s.fi]){
            dfs(s.fi, v, roz);
            maxi=max(maxi, podd[s.fi]);
            podd[v]+=podd[s.fi];
        }
    }
    if(maxi<=roz/2 && (roz-podd[v])<=roz/2)
        centr=v;
}
void zlicz(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    wynik=min(wynik, mini[k-akt]+ile);
    for(auto s:g[v]){
        if(s.fi==oj||odw[s.fi]<=st) continue;
        zlicz(s.fi, v, st, akt+s.se, ile+1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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