Submission #756279

#	Time	Username	Problem	Language	Result	Execution time	Memory
756279		amin	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	8 ms	14292 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int pa[100000];
ll ans=0;
set<int>in[100000],out[100000],pain[100000];
int sz[100000];
int par(int x)
{
    if(pa[x]==x)
        return x;

    pa[x]=par(pa[x]);
    return pa[x];
}
void un(int x,int y)
{
    x=par(x);
    y=par(y);
    if(x==y)
    {
        return ;
    }
    if(sz[x]<sz[y])
        swap(x,y);
    ///dont forget the sz[x]+=sz[y];sz[y]=0;
    pa[y]=x;
    ans-=sz[x]*in[x].size();
    ans-=sz[y]*in[y].size();
    for(auto i:in[y])
    {
        if(in[x].find(i)!=in[x].end())
            continue;

        in[x].insert(i);
    }
for(auto i:pain[y])
    pain[x].insert(par(i));
    ans+=in[x].size()*(sz[x]+sz[y]);
    for(auto i:out[y])
    {
        if(out[x].find(i)!=out[x].end())
            continue;
    out[x].insert(i);
    pain[par(i)].erase(y);
    pain[par(i)].insert(x);
    }
    sz[x]+=sz[y];
    sz[y]=0;

}
int main()
{
    //os_base::sync_with_stdio(0);
    cout.tie(0);
    int n;
    cin>>n;
    int m;
    ans=n;
    for(int i=0;i<n;i++)
    {
        sz[i]=1;
        pa[i]=i;
        in[i].insert(i);

    }
    cin>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        x--;
        y--;

        if(par(x)==par(y))
        {
         //   cout<<1<<' ';
            cout<<ans-n<<endl;
            continue;
        }
        if(pain[par(x)].find(par(y))!=pain[par(x)].end())
        {
            //cout<<' '<<2<<' ';

            un(x,y);
            cout<<ans-n<<endl;
            continue;
        }
        if(in[par(y)].find(x)!=in[par(y)].end())
        {
            //cout<<3<<' ';
            cout<<ans-n<<endl;
            continue;
        }

        in[par(y)].insert(x);
        out[par(x)].insert(y);
        pain[par(y)].insert(par(x));
        ans+=sz[par(y)];
        //cout<<4<<' ';
        cout<<ans-n<<endl;
    }
}

Compilation message (stderr)

joitter2.cpp: In function 'void un(int, int)':
joitter2.cpp:39:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   39 | for(auto i:pain[y])
      | ^~~
joitter2.cpp:41:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   41 |     ans+=in[x].size()*(sz[x]+sz[y]);
      |     ^~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83