Submission #104518

#	Time	Username	Problem	Language	Result	Execution time	Memory
104518		Pajaraja	Mergers (JOI19_mergers)	C++17	100 / 100	1468 ms	84856 KiB

mergers

#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
vector<int> g[MAXN];
int mi[MAXN],mo[MAXN],fa[MAXN],in[MAXN],out[MAXN],mif[MAXN],mof[MAXN],res,t,cnt;
bool c[MAXN];
void dfs1(int s,int f)
{
	in[s]=++t;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs1(g[s][i],s);
	out[s]=++t;
}
void dfs2(int s,int f)
{
	mi[s]=mif[fa[s]]; mo[s]=mof[fa[s]];
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs2(g[s][i],s);
	mi[f]=min(mi[f],mi[s]);
	mo[f]=max(mo[f],mo[s]);
	if(mi[s]==in[s] && out[s]==mo[s] && s!=1) c[s]=true;
}
bool dfs3(int s,int f)
{
	bool d=false;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(dfs3(g[s][i],s)) d=true;
	if(c[s] && !d) {res++; return true;}
	if(d) return true;
	return false;
}
void dfs4(int s,int f)
{
	if(c[s]) {cnt++; return;};
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs4(g[s][i],s);
}
int main()
{
	int n,k; scanf("%d %d",&n,&k);
	for(int i=0;i<n-1;i++) {int t1,t2; scanf("%d%d",&t1,&t2); g[t1].push_back(t2); g[t2].push_back(t1);}
	for(int i=1;i<=n;i++) scanf("%d",&fa[i]);
	dfs1(1,1);
	fill(mif,mif+MAXN,MAXN);
	for(int i=1;i<=n;i++) mif[fa[i]]=min(mif[fa[i]],in[i]);
	for(int i=1;i<=n;i++) mof[fa[i]]=max(mof[fa[i]],out[i]);
	dfs2(1,1);
	dfs3(1,1);
	dfs4(1,1);
	if(cnt==1) res++;
	printf("%d",(res+1)/2);
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs1(int, int)':
mergers.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs1(g[s][i],s);
              ~^~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int, int)':
mergers.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs2(g[s][i],s);
              ~^~~~~~~~~~~~
mergers.cpp: In function 'bool dfs3(int, int)':
mergers.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(dfs3(g[s][i],s)) d=true;
              ~^~~~~~~~~~~~
mergers.cpp: In function 'void dfs4(int, int)':
mergers.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs4(g[s][i],s);
              ~^~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:36:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,k; scanf("%d %d",&n,&k);
           ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:37:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n-1;i++) {int t1,t2; scanf("%d%d",&t1,&t2); g[t1].push_back(t2); g[t2].push_back(t1);}
                                     ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:38:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&fa[i]);
                        ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30