oj.uz

Submission #269191

# Submission time Handle Problem Language Result Execution time Memory
269191 2020-08-17T05:38:40 Z 문홍윤(#5112) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 9 ms 10496 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

int n, m;
set<pii> edg;
LL ans;

int par[100010], sz[100010];
set<pii> od[100010];
set<int> id[100010];

void init(){for(int i=1; i<=100000; i++){par[i]=i, sz[i]=1;}}
int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}

void mergepar(int a, int b){
    int pa=findpar(a), pb=findpar(b);
    if(pa==pb)return;
    bool flg=false;
    if(edg.find(mp(b, a))!=edg.end())flg=true;
    edg.insert(mp(a, b));
    if(!flg){
        ans-=(LL)sz[pb]*id[pb].size();
        id[pb].insert(a);
        od[pa].insert(mp(a, b));
        ans+=(LL)sz[pb]*id[pb].size();
    }
    else{
        ans-=(LL)sz[pa]*id[pa].size();
        ans-=(LL)sz[pb]*id[pb].size();
        ans-=(LL)sz[pa]*(sz[pa]-1);
        ans-=(LL)sz[pb]*(sz[pb]-1);
        if(id[pa].size()+od[pa].size()<=id[pb].size()+od[pb].size()){
            swap(pa, pb);
            swap(a, b);
        }
        vector<pii> del;
        for(auto i:od[pa]){
            if(findpar(i.S)==pb)del.eb(i);
        }
        for(auto i:del){
            od[pa].erase(i);
            id[pb].erase(i.F);
        }
        vector<int> del2;
        for(auto i:id[pa]){
            if(findpar(i)==pb)del2.eb(i);
        }
        for(auto i:del2){
            id[pa].erase(i);
        }
        par[pa]=pb;
        sz[pb]+=sz[pa];
        for(auto i:od[pa])od[pb].insert(i);
        for(auto i:id[pa])id[pb].insert(i);
        ans+=(LL)sz[pb]*id[pb].size();
        ans+=(LL)sz[pb]*(sz[pb]-1);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    init();
    for(int i=1; i<=m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        mergepar(a, b);
        printf("%lld\n", ans);
    }
}

Compilation message

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

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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