oj.uz

Submission #533345

# Submission time Handle Problem Language Result Execution time Memory
533345 2022-03-05T15:02:24 Z DanerZein Road Closures (APIO21_roads) C++14
0 / 100
 514 ms 85496 KB 
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
typedef pair<ii,ll> iii;
const ll MAX=1e16;
const int MAX_N=2e3+10;
bool vis[MAX_N];
vector<vi> G;
int n,ti;
bool orden(ii a,ii b){
  return -a.first+a.second<-b.first+b.second;
}
ll dp[MAX_N][MAX_N];
ll knap(int u,int p,int k){
  if(dp[u][k]!=-1) return dp[u][k];
  vector<ii> op;
  vector<iii> aux;
  ll s=0;
  for(auto &v:G[u]){
    if(v.first!=p){
      if(k>=1){
	op.push_back(ii(knap(v.first,u,ti)+v.second,knap(v.first,u,ti-1)));
	int t=op.size()-1;
	aux.push_back(iii(op[t],v.first));
      }
      s+=knap(v.first,u,ti)+v.second;
    }
  }
  sort(op.begin(),op.end(),orden);
  int c=0;
  for(int i=0;i<op.size();i++){
    if(i<k && -op[i].first+op[i].second<=0) s+=(-op[i].first+op[i].second);
  }
  return dp[u][k]=s;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  n=N;
  vector<ll> res;
  //vector<iii> ed;
  G.resize(n+1);
  for(int i=0;i<n-1;i++){
    int a=U[i],b=V[i],w=W[i];
    G[a].push_back(ii(b,w));
    G[b].push_back(ii(a,w));
    //ed.push_back(iii(ii(a,b),w));
  }
  memset(dp,-1,sizeof dp);
  for(int i=0;i<n;i++){
    ti=i;
    res.push_back(knap(0,0,i));
  }
  return res;
}

Compilation message

roads.cpp: In function 'll knap(int, int, int)':
roads.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<op.size();i++){
      |               ~^~~~~~~~~~
roads.cpp:33:7: warning: unused variable 'c' [-Wunused-variable]
   33 |   int c=0;
      |       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31820 KB Output is correct
2 Correct 444 ms 32324 KB Output is correct
3 Correct 514 ms 32332 KB Output is correct
4 Correct 322 ms 32292 KB Output is correct
5 Correct 15 ms 31868 KB Output is correct
6 Correct 16 ms 31848 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct
8 Correct 256 ms 32248 KB Output is correct
9 Correct 375 ms 32384 KB Output is correct
10 Correct 16 ms 31948 KB Output is correct
11 Correct 15 ms 31948 KB Output is correct
12 Runtime error 64 ms 76512 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31900 KB Output is correct
2 Incorrect 434 ms 42992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31900 KB Output is correct
2 Correct 13 ms 31804 KB Output is correct
3 Correct 14 ms 31856 KB Output is correct
4 Incorrect 15 ms 31948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31900 KB Output is correct
2 Correct 13 ms 31804 KB Output is correct
3 Correct 14 ms 31856 KB Output is correct
4 Incorrect 15 ms 31948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 85496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 85496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31820 KB Output is correct
2 Correct 444 ms 32324 KB Output is correct
3 Correct 514 ms 32332 KB Output is correct
4 Correct 322 ms 32292 KB Output is correct
5 Correct 15 ms 31868 KB Output is correct
6 Correct 16 ms 31848 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct
8 Correct 256 ms 32248 KB Output is correct
9 Correct 375 ms 32384 KB Output is correct
10 Correct 16 ms 31948 KB Output is correct
11 Correct 15 ms 31948 KB Output is correct
12 Runtime error 64 ms 76512 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -