제출 #413031

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
413031	2021-05-28 06:15:08	phathnv	도로 폐쇄 (APIO21_roads)	C++11	100 / 100	457 ms	52348 KiB

roads

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 "roads.h"
using namespace std;
const int N = 1e5;
int k, deg[N];
long long dp[N][2], sum[N], f[N];
multiset<long long> s[N][2];
vector<pair<int, int>> preAdj[N], adj[N];
bool mark[N];
set<int> cur, needVisit;
void Add(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] += val0;
    f[u] += val1 - val0;
    s[u][0].insert(val1 - val0);
}
void Del(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] -= val0;
    if (s[u][0].find(val1 - val0) != s[u][0].end()) {
        f[u] -= val1 - val0;
        s[u][0].erase(s[u][0].find(val1 - val0));
    } else {
        s[u][1].erase(s[u][1].find(val1 - val0));
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22