oj.uz

Submission #278521

# Submission time Handle Problem Language Result Execution time Memory
278521 2020-08-21T13:41:56 Z MKopchev Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 7 ms 9728 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,m;
int parent[nmax],SZ[nmax];

int root(int node)
{
    if(node==parent[node])return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

set< pair<int/*from*/,int/*to component*/> > all[nmax];
set< int > component[nmax];
set< pair<int/*from*/,int/*to*/> > edges_comp;

long long output=0;

int in[nmax];

long long score(int node)
{
    node=root(node);

    return 1LL*SZ[node]*(SZ[node]-1)/2*2+1LL*in[node]*SZ[node];
}
void add(int u,int v)
{
    int u_root=root(u);
    int v_root=root(v);

    if(u_root==v_root)return;

    if(all[u_root].count({u,v_root}))return;

    if(edges_comp.count({v_root,u_root})==0)//do not merge
    {
        output+=SZ[v_root];
        in[v_root]++;

        all[u_root].insert({u,v_root});
        all[v_root].insert({u,v_root});

        edges_comp.insert({u_root,v_root});
        return;
    }
    /*
    if(SZ[u_root]<SZ[v_root])
    {
        swap(u_root,v_root);
        swap(u,v);
    }
    */

    //cout<<u_root<<" "<<u<<" "<<v_root<<" "<<v<<endl;

    //merge
    output=output-score(u_root)-score(v_root);

    for(auto p:all[v_root])
    {
        pair<int,int> k=p;
        if(k.second==v_root)
        {
            k.second=u_root;

            if(all[u_root].count(k)==0)in[u_root]++;

            all[u_root].insert(k);
            all[root(k.first)].insert(k);

            edges_comp.insert({root(k.first),u_root});
        }
        else if(component[v_root].count(k.first)==0)
        {
            //if(all[u_root].count({u_root,root(k.second)})==0)output+=SZ[u_root];in[root(k.second)]++;

            all[u_root].insert({k.first,root(k.second)});
            all[root(k.second)].insert({k.first,root(k.second)});

            edges_comp.insert({u_root,root(k.second)});
        }
        else
        {
            in[u_root]--;
        }
    }

    set< pair<int/*from*/,int/*to component*/> > mem_all=all[v_root];

    all[v_root]={};

    SZ[u_root]+=SZ[v_root];
    parent[v_root]=u_root;

    output+=score(u_root);

    for(auto k:component[v_root])
        component[u_root].insert(k);

    for(auto k:mem_all)
        if(k.second==v_root)add(k.first,u_root);
}
int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)parent[i]=i,SZ[i]=1,component[i]={i};

    for(int i=1;i<=m;i++)
    {
        int u,v;

        scanf("%i%i",&u,&v);

        add(u,v);

        printf("%lld\n",output);
    }
    return 0;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joitter2.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%i%i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -