제출 #756294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756294		amin	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	1718 ms	110068 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;
#define ll long long

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

    pa[x]=par(pa[x]);
    return pa[x];
}
void un(ll x,ll 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);
    }

pa[y]=x;
    sz[x]+=sz[y];
    sz[y]=0;
    for(auto i:in[y])
    {
        if(pain[par(i)].find(x)!=pain[par(i)].end())
            un(x,i);
    }
    for(auto i:out[y])
    {
        if(pain[x].find(par(i))!=pain[x].end())
        un(x,i);

    }

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

    }
    cin>>m;
    while(m--)
    {
        ll 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;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'void un(long long int, long long 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: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83