oj.uz

Submission #604435

# Submission time Handle Problem Language Result Execution time Memory
604435 2022-07-25T06:27:03 Z temporary_juggernaut Mergers (JOI19_mergers) C++14
0 / 100
 206 ms 73484 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,k;
vector<int>g[500005];
int sz[500005];
int gp[500005];
set<int>st[500005];
int pivot[500005];
int sub[500005];
void add(int a,int b){
	if(st[a].size()<st[b].size()){
		swap(st[a],st[b]);
		swap(pivot[a],pivot[b]);
	}
	for(int to:st[b]){
		if(!st[a].count(to)){
			st[a].insert(to);
			pivot[a]+=sz[to];
		}
	}
	st[b].clear();
}
int tot;
int sweet[500005];
map<int,int>mp[500005];
void dfs(int v,int p){
	pivot[v]=sz[gp[v]];
	sub[v]=1;
	st[v].insert(gp[v]);
	for(int to:g[v])if(to^p){
		dfs(to,v);
		if(sub[to]==pivot[to]){
			mp[v][to]=true;
			sweet[v]++;
			tot++;
		}
		sweet[v]+=sweet[to];
		add(v,to);
		sub[v]+=sub[to];
	}
}
int ans;
void go(int v,int p){
	for(int to:g[v])if(to^p){
		go(to,v);
		if(mp[v][to]){
			if(sweet[to]>0&&tot-sweet[v]>0){
				ans--;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i^n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&gp[i]);
		sz[gp[i]]++;
	}
	dfs(1,1);
	ans=tot;
	go(1,1);
	cout<<(ans+1>>1);
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |  cout<<(ans+1>>1);
      |         ~~~^~
mergers.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
mergers.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
mergers.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d",&gp[i]);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58964 KB Output is correct
2 Correct 28 ms 59036 KB Output is correct
3 Correct 33 ms 59044 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 26 ms 59052 KB Output is correct
6 Correct 28 ms 58964 KB Output is correct
7 Correct 27 ms 58964 KB Output is correct
8 Correct 30 ms 59044 KB Output is correct
9 Incorrect 31 ms 59044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58964 KB Output is correct
2 Correct 28 ms 59036 KB Output is correct
3 Correct 33 ms 59044 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 26 ms 59052 KB Output is correct
6 Correct 28 ms 58964 KB Output is correct
7 Correct 27 ms 58964 KB Output is correct
8 Correct 30 ms 59044 KB Output is correct
9 Incorrect 31 ms 59044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58964 KB Output is correct
2 Correct 28 ms 59036 KB Output is correct
3 Correct 33 ms 59044 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 26 ms 59052 KB Output is correct
6 Correct 28 ms 58964 KB Output is correct
7 Correct 27 ms 58964 KB Output is correct
8 Correct 30 ms 59044 KB Output is correct
9 Incorrect 31 ms 59044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 68404 KB Output is correct
2 Correct 206 ms 73484 KB Output is correct
3 Incorrect 32 ms 59396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 58964 KB Output is correct
2 Correct 28 ms 59036 KB Output is correct
3 Correct 33 ms 59044 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 26 ms 59052 KB Output is correct
6 Correct 28 ms 58964 KB Output is correct
7 Correct 27 ms 58964 KB Output is correct
8 Correct 30 ms 59044 KB Output is correct
9 Incorrect 31 ms 59044 KB Output isn't correct
10 Halted 0 ms 0 KB -