Submission #97276

#	Time	Username	Problem	Language	Result	Execution time	Memory
97276		MvC	Friend (IOI14_friend)	C++11	0 / 100	5 ms	2688 KiB

friend

#pragma GCC optimize("O3")
#include "friend.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int p[nmax],sz[nmax],mx,nd;
vector<int>a[nmax];
int fnd(int x)
{
    if(p[x]==x)return x;
    return p[x]=fnd(p[x]);
}
void uni(int x,int y)
{
    x=fnd(x);
    y=fnd(y);
    if(x!=y)
    {
        if(sz[x]<sz[y])swap(x,y);
        p[y]=x;
        sz[x]+=sz[y];
    }
}
void dfs(int x,int p,int d)
{
	if(mx<d)
	{
		mx=d;
		nd=x;
	}
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==p)continue;
		dfs(a[x][i],x,d+1);
	}
}
int findSample(int n,int c[],int h[],int pr[])
{
	int i,j;
	for(i=0;i<n;i++)p[i]=i,sz[i]=1;
	for(i=1;i<n;i++)
	{
		if(pr[i]==0 && fnd(i)!=fnd(h[i]))
		{
			uni(i,h[i]);
			a[h[i]].pb(i);
			a[i].pb(h[i]);
		}
		else
		{
			for(j=0;j<a[h[i]].size();i++)
			{
				if(fnd(i)!=fnd(a[h[i]][j]))
				{
					a[a[h[i]][j]].pb(i);
					a[i].pb(a[h[i]][j]);
					uni(i,a[h[i]][j]);
				}
			}
		}
	}
	dfs(0,-1,0);
	mx=0;
	dfs(nd,-1,0);
	return (mx+1)/2;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
    return 0;
}*/

Compilation message (stderr)

friend.cpp: In function 'void dfs(int, int, int)':
friend.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<a[h[i]].size();i++)
            ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31