oj.uz

Submission #654733

# Submission time Handle Problem Language Result Execution time Memory
654733 2022-11-01T12:00:49 Z Sam_a17 Road Closures (APIO21_roads) C++14
0 / 100
 2000 ms 23092 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
// const long long inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, long long>> adj[N];
long long dp[N][2];

void dfs(int node, int parent, int max_deg) {
  int cnt = 0;
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    dfs(i.first, node, max_deg);
    cnt++;
  }

  if(cnt == 0) {
    dp[node][0] = dp[node][1] = 0;
  } else {
    vector<pair<long long, long long>> diff;
    for(auto i: adj[node]) {
      if(i.first == parent) continue;
      diff.push_back({dp[i.first][1] + i.second - dp[i.first][0], i.first});
    }
    sort(all(diff));
    

    int curr_deg = adj[node].size();
    if(max_deg >= curr_deg) {
      long long to_add = 0; 
      for(int i = 0; i < sz(diff); i++) {
        if(diff[i].first < 0) {
          long long edge = diff[i].first - dp[diff[i].second][1];
          edge += dp[diff[i].second][0];

          //
          to_add += dp[diff[i].second][1] + edge;
        } else {
          to_add += dp[diff[i].second][0];
        }
      }

      dp[node][0] = dp[node][1] = to_add;
    } else {
      {
        int qn = curr_deg - max_deg;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];

            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }

        assert(cr == qn);
        dp[node][0] = to_add; 
      }

      {
        int qn = curr_deg - max_deg - 1;
        long long to_add = 0, cr = 0; 
        for(int i = 0; i < sz(diff); i++) {
          if(diff[i].first < 0) {
            long long edge = diff[i].first - dp[diff[i].second][1];
            edge += dp[diff[i].second][0];

            //
            to_add += dp[diff[i].second][1] + edge;
            cr++;
          } else {
            if(cr < qn) {
              to_add += diff[i].first + dp[diff[i].second][0];
              cr++;
            } else{
              to_add += dp[diff[i].second][0];
            }
          }
        }

        if(cr == qn) {
          dp[node][1] = to_add; 
          dp[node][0] = max(dp[node][0], to_add);
        }
      }
    }
  }
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  bool flag1 = true, flag2 = true;;
  for(int i = 0; i < N - 1; i++) {
    if(U[i] != 0) {
      flag1 = false;
    }
 
    if(U[i] != i || V[i] != i + 1) {
      flag2 = false;
    }
  }
 
  // if(flag1) {
  //   sort(all(W));
  //   vector<long long> answ(N, 0);
  //   int it = 0;
  //   for(int i = N - 2; i >= 0; i--) {
  //     answ[i] = answ[i + 1] + W[it++];
  //   }
 
  //   return answ;
  // }
 
  // if(flag2) {
  //   vector<long long> answ(N, 0);
  //   for(auto i: W) {
  //     answ[0] += i;
  //   }
 
  //   vector<vector<long long>> dp(N, vector<long long> (2, 0));
  //   dp[0][0] = 0;
  //   dp[0][1] = 0;
  
  //   for(int i = 1; i < N; i++) {
  //     dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + W[i - 1];
  //     dp[i][1] = dp[i - 1][0];
  //   }
 
  //   answ[1] = min(dp[N - 1][0], dp[N - 1][1]);
  //   return answ;
  // }

  for(int i = 0; i < N - 1; i++) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }

  vector<long long> answ(N, 0);
  for(auto i: W) {
    answ[0] += i;
  }

  for(int i = 1; i < N; i++) {
    dfs(0, -1, i);
    answ[i] = dp[0][0];
  }
 
  return answ;
}

Compilation message

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:103:8: warning: variable 'flag1' set but not used [-Wunused-but-set-variable]
  103 |   bool flag1 = true, flag2 = true;;
      |        ^~~~~
roads.cpp:103:22: warning: variable 'flag2' set but not used [-Wunused-but-set-variable]
  103 |   bool flag1 = true, flag2 = true;;
      |                      ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 200 ms 5232 KB Output is correct
3 Correct 226 ms 5232 KB Output is correct
4 Correct 231 ms 5204 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 5 ms 4948 KB Output is correct
8 Correct 183 ms 5204 KB Output is correct
9 Correct 267 ms 5244 KB Output is correct
10 Correct 4 ms 4968 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Execution timed out 2085 ms 12792 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 2084 ms 23092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 14812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 14812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 200 ms 5232 KB Output is correct
3 Correct 226 ms 5232 KB Output is correct
4 Correct 231 ms 5204 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 5 ms 4948 KB Output is correct
8 Correct 183 ms 5204 KB Output is correct
9 Correct 267 ms 5244 KB Output is correct
10 Correct 4 ms 4968 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Execution timed out 2085 ms 12792 KB Time limit exceeded
13 Halted 0 ms 0 KB -