Submission #448698

#	Time	Username	Problem	Language	Result	Execution time	Memory
448698		MOUF_MAHMALAT	Izlet (COI19_izlet)	C++14	0 / 100	810 ms	35792 KiB

izlet

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,a[3009][3009],p[3009],sz[3009],c[3009],o,op,t;
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return;
    if(sz[y]>sz[x])
        swap(x,y);
    p[y]=x;
    sz[x]+=sz[y];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    scanf("%d%d",&t,&n);
    for(ll i=1; i<=n; i++)
        p[i]=i,sz[i]=1;
    for(ll i=1; i<=n; i++)
        for(ll j=1; j<=n; j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==1)
                mrg(i,j);
        }
    for(ll i=1; i<=n; i++)
    {
        if(c[gp(i)]==0)
            c[gp(i)]=++o;
        printf("%d ",c[gp(i)]);
    }
    printf("\n");
    op=gp(1);
    for(ll i=1; i<=n; i++)
    {
        if(i!=gp(i))
            printf("%d %d\n",i,gp(i));
        else if(i!=op)
            printf("%d %d\n",i,op);
    }
    return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d",&t,&n);
      |     ~~~~~^~~~~~~~~~~~~~
izlet.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%d",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57