oj.uz

Submission #533110

# Submission time Handle Problem Language Result Execution time Memory
533110 2022-03-04T20:23:33 Z DanerZein Road Closures (APIO21_roads) C++14
0 / 100
 2000 ms 23672 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];
int ti;
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);
      if(!issameset(v.first,u)) ans+=v.second;
    }
  }
  ll s=ans;
  int id=-1;
  for(auto &v:G[u]){
    if(v.first!=p && !issameset(v.first,u)){
      ll rp=s;
      rp=rp-dp[v.first]-v.second;
      for(auto &z:G[v.first]){
	if(z.first!=u && !issameset(z.first,v.first)){
	  rp+=dp[z.first];
	  if(!issameset(z.first,v.first))
	     rp+=z.second;
	}
      }
      if(ans>rp){
	ans=rp;
	id=v.first;
      }
    }
  }
  path[u]=id;
  return dp[u]=ans;
}
void dfs(int u,int p){
  for(auto &v:G[u]){
    if(v.first!=p && v.first!=path[u]) dfs(v.first,u);
  }
  if(path[u]!=-1){
    unionset(u,path[u]);
    for(auto &v:G[path[u]]){
      if(v.first!=u){
	dfs(v.first,path[u]);
      }
    }
  }
}
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++){
    ti=i;
    memset(dp,-1,sizeof dp);
    memset(path,-1,sizeof path);
    res.push_back(knap(0,0));
    dfs(0,0);
  }
  return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 204 ms 2928 KB Output is correct
3 Correct 246 ms 2936 KB Output is correct
4 Correct 213 ms 2892 KB Output is correct
5 Correct 9 ms 2672 KB Output is correct
6 Correct 13 ms 2676 KB Output is correct
7 Correct 13 ms 2684 KB Output is correct
8 Correct 178 ms 2892 KB Output is correct
9 Correct 261 ms 2920 KB Output is correct
10 Correct 14 ms 2636 KB Output is correct
11 Correct 14 ms 2684 KB Output is correct
12 Execution timed out 2056 ms 10224 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 2636 KB Output is correct
2 Execution timed out 2041 ms 23672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2608 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 10 ms 2636 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 2084 ms 15576 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 2084 ms 15576 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 2636 KB Output is correct
2 Correct 204 ms 2928 KB Output is correct
3 Correct 246 ms 2936 KB Output is correct
4 Correct 213 ms 2892 KB Output is correct
5 Correct 9 ms 2672 KB Output is correct
6 Correct 13 ms 2676 KB Output is correct
7 Correct 13 ms 2684 KB Output is correct
8 Correct 178 ms 2892 KB Output is correct
9 Correct 261 ms 2920 KB Output is correct
10 Correct 14 ms 2636 KB Output is correct
11 Correct 14 ms 2684 KB Output is correct
12 Execution timed out 2056 ms 10224 KB Time limit exceeded
13 Halted 0 ms 0 KB -