oj.uz

답안 #278573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278573 2020-08-21T14:42:55 Z MKopchev 조이터에서 친구를 만드는건 재밌어 (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)
{
    /*
    cout<<"\n\n\n"<<endl;

    cout<<"add "<<u<<" "<<v<<" "<<output<<endl;

    cout<<"edges_comp"<<endl;
    for(auto k:edges_comp)cout<<k.first<<" "<<k.second<<endl;

    for(int i=1;i<=n;i++)
    {
        cout<<i<<" -> "<<in[i]<<" "<<root(i)<<" "<<SZ[root(i)]<<endl;
        cout<<"all: "<<endl;
        for(auto j:all[i])cout<<j.first<<" "<<j.second<<endl;
        cout<<"component: ";for(auto k:component[i])cout<<k<<" ";cout<<endl;

        cout<<"---"<<endl;
    }
    */

    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);
    }
    */

    edges_comp.erase({u_root,v_root});
    edges_comp.erase({v_root,u_root});

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

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

    //cout<<"after sub "<<output<<endl;

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

    for(auto p:mem_all)
    {
        int where=-1;

        pair<int,int> k=p;

        //cout<<"moving "<<k.first<<" "<<k.second<<endl;

        if(k.second==v_root&&component[u_root].count(k.first))
        {
            all[u_root].erase({k.first,v_root});
            all[v_root].erase({k.first,v_root});

            in[v_root]--;

            where=1;
        }
        else if(k.second==v_root)
        {
            all[root(k.first)].erase(k);

            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});
            edges_comp.erase({root(k.first),v_root});

            where=2;
        }

        else if(component[u_root].count(k.second)==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)});

            /*
            cout<<"Wrong "<<endl;
            system("pause");
            */

            where=3;
        }
        else
        {
            in[u_root]--;

            all[u_root].erase({k.first,u_root});
            all[v_root].erase({k.first,u_root});

            where=4;
        }
        //cout<<"where= "<<where<<" "<<in[u_root]<<endl;
    }

    all[v_root]={};
    in[v_root]=0;

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

    output+=score(u_root);

    //cout<<"after add "<<output<<endl;

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

    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 'void add(int, int)':
joitter2.cpp:90:13: warning: variable 'where' set but not used [-Wunused-but-set-variable]
   90 |         int where=-1;
      |             ^~~~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joitter2.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |         scanf("%i%i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Incorrect 7 ms 9728 KB Output isn't correct
4 Halted 0 ms 0 KB -