| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97277 |
2019-02-14T17:42:50 Z |
MvC |
Friend (IOI14_friend) |
C++11 |
|
5 ms |
2688 KB |
#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,v[nmax];
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)
{
v[x]=1;
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,ans=0;
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]);
}
}
}
}
for(i=0;i<n;i++)
{
if(v[i])continue;
dfs(i,-1,0);
ans=max(ans,mx);
mx=nd=0;
dfs(nd,-1,0);
ans=max(ans,mx);
mx=nd=0;
}
return (ans+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
friend.cpp: In function 'void dfs(int, int, int)':
friend.cpp:45: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:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<a[h[i]].size();i++)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
