oj.uz

답안 #1083442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083442 2024-09-03T07:22:53 Z LucasLe Magic Tree (CEOI19_magictree) C++17
0 / 100
 5 ms 7516 KB 
#include <bits/stdc++.h>


#define                int  long long
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}

int bin_pow(int x, int y) {
  int res=1;
  while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}
  return res;
}

const int INF = 1e17;
const int maxn = 1e5 + 5;

int N, M, K;
int day[maxn + 5], weight[maxn + 5];
map<int, int> f[maxn + 5];
vector<int> g[maxn + 5];

void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    if (f[v].size() > f[u].size()) swap(f[v], f[u]);
    for (auto it : f[v]) f[u][it.first] += it.second;
    f[v].clear();
  }
  if (day[u] && weight[u]) {
    int s = 0;
    while (true) {
      auto it = f[u].upper_bound(day[u]);
      if (it == f[u].end()) break;
      if (it->second + s <= weight[u]) {
        s += it->second;
        f[u].erase(it);
      } else {
        it->second += s - weight[u];
        break;
      }
    }
    f[u][day[u]] += weight[u];
  }
}

void solve(int tc) {
  // trong 1 subtree, neu chon dinh thi nhung dinh a[v] > a[u] ko chon
  // con ko chon dinh u thi chon cac dinh a[v] > a[u]
  
  cin >> N >> M >> K;
  rep(i, 2, N) {
    int p; cin >> p;
    g[p].push_back(i);
  }
  rep(i, 1, M) {
    int v, d, w; cin >> v >> d >> w;
    day[v] = d;
    weight[v] = w;
  }
  dfs(1);
  int ans = 0;
  for (auto it : f[1]) {
    ans += it.second;
  }
  cout << ans << '\n';
}

signed main() {

#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin); 
  // freopen("SDS.INP", "r", stdin);
  // freopen("SDS.OUT", "w", stdout);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) {
    solve(i);
  }
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -