제출 #373764

#제출 시각UTC-0아이디문제언어결과실행 시간메모리
3737642021-03-05 16:30:42lohachoConstruction of Highway (JOI18_construction)C++14
100 / 100
795 ms22636 KiB
#include <bits/stdc++.h>
using namespace std;
const int NS = (int)1e5 + 4;
int n, c[NS];
vector<int> way[NS];
int sz[NS], in[NS], incnt, up[NS], pr[NS];
pair<int, int> que[NS];
vector<pair<int, int>> block;
void dfs_sz(int x, int from){
sz[x] = 1; pr[x] = from;
for(auto&nxt:way[x]){
if(nxt == from){
continue;
}
dfs_sz(nxt, x);
sz[x] += sz[nxt];
if(way[x][0] == from || sz[way[x][0]] < sz[nxt]){
swap(way[x][0], nxt);
}
}
}
void dfs_hld(int x, int from){
in[x] = incnt++;
for(auto&nxt:way[x]){
if(nxt == from){
continue;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...