oj.uz

Submission #533098

# Submission time Handle Problem Language Result Execution time Memory
533098 2022-03-04T19:10:58 Z DanerZein Road Closures (APIO21_roads) C++14
0 / 100
 2000 ms 18784 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 int MAX_N=2e5+10;
bool vis[MAX_N];
int pa[MAX_N];
vector<vi> G;
int n;
void init(int n){
  for(int i=0;i<n;i++)
    pa[i]=i;
}
int findset(int x){
  if(pa[x]==x) return x;
  return pa[x]=findset(pa[x]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
  }
}
ll dp[MAX_N];
int path[MAX_N];
ll knap(int u,int p){
  if(dp[u]!=-1) return dp[u];
  ll ans=0;
  for(auto &v:G[u]){
    if(v.first!=p){
      ans+=knap(v.first,u)+v.second;
    }
  }
  ll s=ans;
  int id=-1;
  for(auto &v:G[u]){
    if(v.first!=p){
      ll rp=s;
      rp=rp-dp[v.first]-v.second;
      for(auto &z:G[v.first]){
	if(z.first!=u){
	  rp+=dp[z.first]+z.second;
	}
      }
      if(ans>rp){
	ans=rp;
	id=v.first;
      }
    }
  }
  path[u]=id;
  return dp[u]=ans;
}
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);
  ll s=0;
  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));
    s+=w;
  }
  res.push_back(s);
  init(n);
  for(int i=0;i<n-1;i++){
    memset(dp,-1,sizeof dp);
    res.push_back(knap(findset(0),findset(0)));
    for(int j=0;j<n;j++){
      if(path[j]!=-1) unionset(j,path[j]);
    }
    G.clear(); G.resize(n+1);
    for(int j=0;j<ed.size();j++){
      int u=findset(ed[j].first.first);
      int v=findset(ed[j].first.second);
      ll w=ed[j].second;
      if(u!=v){
	G[u].push_back(ii(v,w));
	G[v].push_back(ii(u,w));
      }
    }
  }
  return res;
}

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:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int j=0;j<ed.size();j++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 280 ms 2176 KB Output is correct
3 Correct 308 ms 2188 KB Output is correct
4 Correct 306 ms 2188 KB Output is correct
5 Correct 8 ms 1868 KB Output is correct
6 Correct 11 ms 1868 KB Output is correct
7 Correct 11 ms 1900 KB Output is correct
8 Correct 221 ms 2148 KB Output is correct
9 Correct 290 ms 2168 KB Output is correct
10 Correct 10 ms 1868 KB Output is correct
11 Correct 10 ms 1868 KB Output is correct
12 Execution timed out 2065 ms 10452 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Incorrect 9 ms 1868 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 2075 ms 14660 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 2075 ms 14660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 280 ms 2176 KB Output is correct
3 Correct 308 ms 2188 KB Output is correct
4 Correct 306 ms 2188 KB Output is correct
5 Correct 8 ms 1868 KB Output is correct
6 Correct 11 ms 1868 KB Output is correct
7 Correct 11 ms 1900 KB Output is correct
8 Correct 221 ms 2148 KB Output is correct
9 Correct 290 ms 2168 KB Output is correct
10 Correct 10 ms 1868 KB Output is correct
11 Correct 10 ms 1868 KB Output is correct
12 Execution timed out 2065 ms 10452 KB Time limit exceeded
13 Halted 0 ms 0 KB -