oj.uz

Submission #832057

# Submission time Handle Problem Language Result Execution time Memory
832057 2023-08-20T21:47:13 Z Antekb Road Closures (APIO21_roads) C++17
14 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
#include "roads.h"
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii > vii;

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=1e5+5;
vii E[N], E2[N];
ll dp[N][2];
int par[N];
int vis[N];
vi co[N];
vector<ll> suf[N];

void dfs(int v, int k){
	for(pii e:E[v]){
		int u=e.st, c=e.nd;
		if(u!=par[v]){
			par[u]=v;
			dfs(u, k);
		}
	}
	dp[v][1]=dp[v][0]=0;
		vector<int> V;
		for(pii e:E[v]){
			int u=e.st, c=e.nd;
			if(u!=par[v]){
					dp[v][0]+=dp[u][1];
					V.pb(dp[u][0]+c-dp[u][1]);
			}
		}
		sort(all(V));
		for(int j=V.size()-1; j>=int(V.size())-k+1 && j>=0 && V[j]>0; j--){
			dp[v][0]+=V[j];
		}
		dp[v][1]=dp[v][0];
		if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
		//if(i>=2)assert(2*dp[v][1][i-1]>=dp[v][1][i]+dp[v][1][i-2]);
	//deb(v, dp[v][0], dp[v][1], dp[v][2]);
}
void dfs2(int v, int k){
	for(pii e:E2[v])dfs2(e.st, k);
	dp[v][1]=dp[v][0]=0;
	vector<int> V;
	for(pii e:E2[v]){
		int u=e.st, c=e.nd;
		dp[v][0]+=dp[u][1];
		V.pb(dp[u][0]+c-dp[u][1]);
	}
	sort(all(V));
	ll s=0;
	ll opt=0, opt2=0;
	dp[v][1]=dp[v][0];
	/*for(int i:V){
		deb(i);
	}
	deb(" ");
	for(int i:suf[v]){
		deb(i);
	}*/
	if(suf[v].size()){
	for(int j=0; j<=V.size(); j++){
		if(j+1<k){
			opt=max(opt, suf[v].end()[max(-k+1+j, -int(suf[v].size()))]+s);
			//deb(j, s, suf[v].end()[-k+1+j]);
		}
		if(j<k)opt2=max(opt2, suf[v].end()[max(-k+j, -int(suf[v].size()))]+s);
		if(j!=V.size())s+=V.end()[-1-j];
	}
	}
	else{
		for(int j=0; j<=k && j<=V.size(); j++){
		if(j+1<=k){
			opt=max(opt,s);
			//deb(j, s, suf[v].end()[-k+1+j]);
		}
		if(j<=k)opt2=max(opt2, s);
		if(j!=V.size())s+=V.end()[-1-j];
	}
	}
	opt2=max(opt, opt2);
	dp[v][0]+=opt;
	dp[v][1]+=opt2;
	//deb(v, dp[v][0], dp[v][1]);
}

std::vector<long long> minimum_closure_costs(int n, std::vector<int> uu, 
	std::vector<int> vv,std::vector<int> ww) {
	ll sum=0;
	vi stop;
	for(int i=0; i<n-1; i++){
		E[uu[i]].eb(vv[i], ww[i]);
		E[vv[i]].eb(uu[i], ww[i]);
		sum+=ww[i];
	}
	for(int i=0; i<n; i++){
		stop.pb(E[i].size());
		sort(all(E[i]), [](pii a, pii b){return mp(a.nd, a.st)<mp(b.nd, b.st);});
	}
	sort(all(stop));
	reverse(all(stop));
	int kk=1;
	while(kk<n)kk*=2;
	kk/=128;
	vector<ll> ans(n);
	ans[0]=sum;
	par[0]=-1;
	int K=stop[kk];
	for(int i=1; i<K && i<n; i++){
		dfs(0, i);
		ans[i]=sum-dp[0][1];
	}
	vi todo;
	for(int t=K; t<n; t++){
		if((t==K || kk>30) && t==stop[kk]){
			deb(t);
			while(kk && stop[kk]==t)kk/=2;
			todo.clear();
			sum=0;
			for(int i=0; i<n; i++){
				if(E[i].size()>=K){
					E2[i].clear();
					suf[i].clear();
					co[i].clear();
					if(i==0 || E[par[i]].size()<K)todo.pb(i);
					for(auto e:E[i]){
						if(E[e.st].size()>=K && e.st!=par[i]){
							//deb(i, par[i], e.st);
							E2[i].pb(e);
						}
						if(E[e.st].size()<K || e.st!=par[i]){
							sum+=e.nd;
							if(E[e.st].size()<K){
								co[i].pb(e.nd);
							}
						}
					}
					//if(co[i].size())sort(all(co[i]));
					suf[i].resize(co[i].size());
					for(int j=int(co[i].size())-1; j>=0; j--){
						suf[i][j]=co[i][j];
						if(j!=co[i].size()-1){
							suf[i][j]+=suf[i][j+1];
						}
					}
				}
			}
		}
				ans[t]=sum;
				for(int v:todo){
					dfs2(v, t);
					ans[t]-=dp[v][1];
				}
	}
	return ans;
}

Compilation message

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:32:15: warning: unused variable 'c' [-Wunused-variable]
   32 |   int u=e.st, c=e.nd;
      |               ^
roads.cpp:52:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
      |      ~~~~~~~~^~~
roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int j=0; j<=V.size(); j++){
      |               ~^~~~~~~~~~
roads.cpp:83:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   if(j!=V.size())s+=V.end()[-1-j];
      |      ~^~~~~~~~~~
roads.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j=0; j<=k && j<=V.size(); j++){
      |                        ~^~~~~~~~~~
roads.cpp:93:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   if(j!=V.size())s+=V.end()[-1-j];
      |      ~^~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:136:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |     if(E[i].size()>=K){
      |        ~~~~~~~~~~~^~~
roads.cpp:140:33: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |      if(i==0 || E[par[i]].size()<K)todo.pb(i);
      |                 ~~~~~~~~~~~~~~~~^~
roads.cpp:142:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |       if(E[e.st].size()>=K && e.st!=par[i]){
      |          ~~~~~~~~~~~~~~^~~
roads.cpp:146:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  146 |       if(E[e.st].size()<K || e.st!=par[i]){
      |          ~~~~~~~~~~~~~~^~
roads.cpp:148:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |        if(E[e.st].size()<K){
      |           ~~~~~~~~~~~~~~^~
roads.cpp:157:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |       if(j!=co[i].size()-1){
      |          ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 70 ms 9896 KB Output is correct
3 Correct 78 ms 9912 KB Output is correct
4 Correct 66 ms 9920 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9624 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 59 ms 9884 KB Output is correct
9 Correct 82 ms 9812 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Execution timed out 2074 ms 16156 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Execution timed out 2065 ms 31044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9700 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9696 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9764 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9700 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9696 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9764 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9724 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 4 ms 9684 KB Output is correct
23 Correct 7 ms 9812 KB Output is correct
24 Correct 7 ms 9812 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 8 ms 9820 KB Output is correct
27 Runtime error 511 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 19040 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 2070 ms 19040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 70 ms 9896 KB Output is correct
3 Correct 78 ms 9912 KB Output is correct
4 Correct 66 ms 9920 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9624 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 59 ms 9884 KB Output is correct
9 Correct 82 ms 9812 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9728 KB Output is correct
12 Execution timed out 2074 ms 16156 KB Time limit exceeded
13 Halted 0 ms 0 KB -