제출 #943489

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
943489	2024-03-11 14:21:03	SoSmolSten	경주 (Race) (IOI11_race)	C++17	100 / 100	261 ms	36944 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"
#define pp pair<int, int>
#define F first
#define S second
using namespace std;
const int SZ = 2e5 + 10, M = 1e6 + 10, INF = 1e9;
vector<pp> graph[SZ];
int mn[M], ti[M], c[SZ], n, k, ans = INF, cnt = 0;
bool del[SZ];
void dfs(int u, int p){
  c[u] = 1;
  for(auto &[v, w] : graph[u]){
    if(v == p || del[v]) continue;
    dfs(v, u);
    c[u] += c[v];
  }
}
void upd(int u, int p, int w, int d){
  if(w > k) return; 
  if(ti[w] != cnt) mn[w] = d;
  else mn[w] = min(mn[w], d);
  ti[w] = cnt;
  
  for(auto &[v, l] : graph[u]){
    if(v == p || del[v]) continue;
    upd(v, u, w + l, d + 1);
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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