oj.uz

Submission #756291

# Submission time Handle Problem Language Result Execution time Memory
756291 2023-06-11T12:28:45 Z amin Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 13 ms 14420 KB 
#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);
    }

pa[y]=x;
    sz[x]+=sz[y];
    sz[y]=0;
    for(auto i:in[y])
    {
        if(pain[i].find(x)!=pain[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);
    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14296 KB Output is correct
4 Correct 8 ms 14396 KB Output is correct
5 Correct 8 ms 14400 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Incorrect 13 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14296 KB Output is correct
4 Correct 8 ms 14396 KB Output is correct
5 Correct 8 ms 14400 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Incorrect 13 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14296 KB Output is correct
4 Correct 8 ms 14396 KB Output is correct
5 Correct 8 ms 14400 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Incorrect 13 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -