제출 #833956

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
833956	2023-08-22 09:46:49	MODDI	Magic Tree (CEOI19_magictree)	C++14	68 / 100	114 ms	29464 KiB

magictree

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>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m, k;
vi G[100100];
vector<pll> fruits;
map<int, int> dp[100100];
void dfs(int node, int p){
//  cout<<"AT: "<<node<<endl;
  for(auto next : G[node]){
    if(next !=p){
      dfs(next, node);
      if(dp[node].size() < dp[next].size()) swap(dp[node], dp[next]);
      for(auto t : dp[next])  dp[node][t.first] += t.second;
    }
  }
  if(fruits[node].first != -1){
    ll hold = fruits[node].second;
    while(hold > 0){
      auto rem = dp[node].upper_bound(fruits[node].first);
      if(rem == dp[node].end()) break;
      if(rem->second <= hold){
        hold -= rem->second;
        dp[node].erase(rem);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 0 / 17