oj.uz

Submission #439725

# Submission time Handle Problem Language Result Execution time Memory
439725 2021-06-30T16:22:07 Z CSQ31 Road Closures (APIO21_roads) C++17
17 / 100
 204 ms 28756 KB 
#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
vii g1(MAXN),g2(MAXN);
vector<int>par(MAXN),szz(MAXN,1),act(MAXN);
vector<ll>ans;
int find(int x){
	if(x == par[x])return x;
	else return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return;
	if(szz[a] > szz[b])swap(a,b);
	par[a] = b;
	szz[b]+=szz[a];
}
int dfs(int v,int u,int k){
	int need = sz(g1[v])-k;
	for(int x:g2[v]){
		if(x != u){
			int res = dfs(x,v,k);
			need-=res;
			ans[k]+=res;
		}
	}
	if(need > 0&& u != -1){
		need--;
		ans[k]+=max(0,need);
		return 1;
	}
	else{
		ans[k]+=max(0,need);
		return 0;
	}
}
vector<ll> minimum_closure_costs(int n, vector<int> u,vector<int>v,vector<int>w){
	bool sub4 = 1;
	ans.resize(n);
	for(int i=0;i<n-1;i++){
		g1[u[i]].pb(v[i]);
		g1[v[i]].pb(u[i]);
		if(w[i]!=1)sub4 = 0;
	}
	if(sub4){
		vector<int>c(n);
		for(int i=0;i<n;i++){c[i] = i;par[i] = i;}
		sort(all(c),[&](int x,int y){return sz(g1[x]) > sz(g1[y]);});
		int ptr = -1;
		vector<int>vis(n);
		for(int i=n-1;i>=0;i--){
			while(ptr+1<n && sz(g1[c[ptr+1]]) > i){
				ptr++;
				int d = c[ptr];
				act[d] = 1;
				for(int x:g1[d]){
					if(act[x]){
						g2[x].pb(d);
						g2[d].pb(x); 
						unite(x,d);
					}
				}
			}
			vector<int>meet;
			for(int j=0;j<=ptr;j++){
				int a = find(c[j]);
				if(vis[a])continue;
				else{
					meet.pb(a);
					dfs(a,-1,i);
					vis[a] = 1;
				}
			}
			for(int x:meet)vis[x] = 0;
		}
		
		
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 21880 KB Output is correct
2 Correct 204 ms 23100 KB Output is correct
3 Correct 121 ms 24864 KB Output is correct
4 Correct 182 ms 23692 KB Output is correct
5 Correct 113 ms 24844 KB Output is correct
6 Correct 109 ms 24352 KB Output is correct
7 Correct 142 ms 24228 KB Output is correct
8 Correct 100 ms 23396 KB Output is correct
9 Correct 134 ms 24716 KB Output is correct
10 Correct 195 ms 23420 KB Output is correct
11 Correct 107 ms 24716 KB Output is correct
12 Correct 109 ms 24384 KB Output is correct
13 Correct 8 ms 11956 KB Output is correct
14 Correct 83 ms 27076 KB Output is correct
15 Correct 99 ms 28756 KB Output is correct
16 Correct 10 ms 12236 KB Output is correct
17 Correct 10 ms 12236 KB Output is correct
18 Correct 9 ms 12200 KB Output is correct
19 Correct 9 ms 12200 KB Output is correct
20 Correct 9 ms 12296 KB Output is correct
21 Correct 86 ms 22792 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 21880 KB Output is correct
2 Correct 204 ms 23100 KB Output is correct
3 Correct 121 ms 24864 KB Output is correct
4 Correct 182 ms 23692 KB Output is correct
5 Correct 113 ms 24844 KB Output is correct
6 Correct 109 ms 24352 KB Output is correct
7 Correct 142 ms 24228 KB Output is correct
8 Correct 100 ms 23396 KB Output is correct
9 Correct 134 ms 24716 KB Output is correct
10 Correct 195 ms 23420 KB Output is correct
11 Correct 107 ms 24716 KB Output is correct
12 Correct 109 ms 24384 KB Output is correct
13 Correct 8 ms 11956 KB Output is correct
14 Correct 83 ms 27076 KB Output is correct
15 Correct 99 ms 28756 KB Output is correct
16 Correct 10 ms 12236 KB Output is correct
17 Correct 10 ms 12236 KB Output is correct
18 Correct 9 ms 12200 KB Output is correct
19 Correct 9 ms 12200 KB Output is correct
20 Correct 9 ms 12296 KB Output is correct
21 Correct 86 ms 22792 KB Output is correct
22 Incorrect 8 ms 12052 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -