oj.uz

Submission #533149

# Submission time Handle Problem Language Result Execution time Memory
533149 2022-03-05T01:38:29 Z DanerZein Road Closures (APIO21_roads) C++14
14 / 100
 2000 ms 84156 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));
  }
  for(int i=0;i<n;i++){
    ti=i;
    memset(dp,-1,sizeof dp);
    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 17 ms 31868 KB Output is correct
2 Execution timed out 2084 ms 32252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31828 KB Output is correct
2 Execution timed out 2097 ms 40140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31820 KB Output is correct
2 Correct 28 ms 31908 KB Output is correct
3 Correct 30 ms 31920 KB Output is correct
4 Correct 520 ms 31920 KB Output is correct
5 Correct 693 ms 32044 KB Output is correct
6 Correct 657 ms 31948 KB Output is correct
7 Correct 619 ms 31932 KB Output is correct
8 Correct 687 ms 31928 KB Output is correct
9 Correct 689 ms 31928 KB Output is correct
10 Correct 594 ms 31956 KB Output is correct
11 Correct 670 ms 31960 KB Output is correct
12 Correct 693 ms 32028 KB Output is correct
13 Correct 489 ms 31940 KB Output is correct
14 Correct 721 ms 31948 KB Output is correct
15 Correct 750 ms 31948 KB Output is correct
16 Correct 365 ms 31920 KB Output is correct
17 Correct 711 ms 31928 KB Output is correct
18 Correct 686 ms 31932 KB Output is correct
19 Correct 646 ms 31952 KB Output is correct
20 Correct 686 ms 31948 KB Output is correct
21 Correct 17 ms 31820 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31820 KB Output is correct
2 Correct 28 ms 31908 KB Output is correct
3 Correct 30 ms 31920 KB Output is correct
4 Correct 520 ms 31920 KB Output is correct
5 Correct 693 ms 32044 KB Output is correct
6 Correct 657 ms 31948 KB Output is correct
7 Correct 619 ms 31932 KB Output is correct
8 Correct 687 ms 31928 KB Output is correct
9 Correct 689 ms 31928 KB Output is correct
10 Correct 594 ms 31956 KB Output is correct
11 Correct 670 ms 31960 KB Output is correct
12 Correct 693 ms 32028 KB Output is correct
13 Correct 489 ms 31940 KB Output is correct
14 Correct 721 ms 31948 KB Output is correct
15 Correct 750 ms 31948 KB Output is correct
16 Correct 365 ms 31920 KB Output is correct
17 Correct 711 ms 31928 KB Output is correct
18 Correct 686 ms 31932 KB Output is correct
19 Correct 646 ms 31952 KB Output is correct
20 Correct 686 ms 31948 KB Output is correct
21 Correct 17 ms 31820 KB Output is correct
22 Correct 17 ms 31844 KB Output is correct
23 Execution timed out 2081 ms 32068 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 84156 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 94 ms 84156 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 17 ms 31868 KB Output is correct
2 Execution timed out 2084 ms 32252 KB Time limit exceeded
3 Halted 0 ms 0 KB -