Submission #406842

#	Time	Username	Problem	Language	Result	Execution time	Memory
406842		urd05	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5078 ms	10060 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
set<int> adj[100000];
set<P> rev[100000];
int p[100000];
int n,m;
set<P> edge;

int find(int a) {
    if (p[a]<0) {
        return a;
    }
    return p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[a]+=p[b];
    p[b]=a;
}

long long func(int x) {
    return (1LL*x*(x-1));
}

int main(void) {
    scanf("%d %d",&n,&m);
    long long ret=0;
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        a--;
        b--;
        if (find(a)==find(b)||adj[a].find(find(b))!=adj[a].end()) {
            printf("%lld\n",ret);
            continue;
        }
        if (edge.find(P(b,a))==edge.end()) {
            adj[a].insert(find(b));
            rev[find(b)].insert(P(find(a),a));
            edge.insert(P(a,b));
            ret+=-p[find(b)];
        }
        else {
            a=find(a);
            b=find(b);
            ret+=(-p[b])*(rev[a].size()-distance(rev[a].lower_bound(P(b+1,-1)),rev[a].lower_bound(P(b,-1))));
            ret+=(-p[a])*(rev[b].size()-distance(rev[b].lower_bound(P(a+1,-1)),rev[b].lower_bound(P(a,-1))));
            ret-=-p[a]*(distance(rev[a].lower_bound(P(b+1,-1)),rev[a].lower_bound(P(b,-1))));
            ret-=-p[b]*(distance(rev[b].lower_bound(P(a+1,-1)),rev[b].lower_bound(P(a,-1))));
            ret-=func(-p[a]);
            ret-=func(-p[b]);
            ret+=func(-p[a]-p[b]);
            if (rev[a].size()>rev[b].size()) {
                for(auto curr:rev[b]) {
                    if (curr.first!=a) {
                        rev[a].insert(curr);
                        adj[curr.second].erase(b);
                        adj[curr.second].insert(a);
                    }
                }
                merge(a,b);
            }
            else {
                for(auto curr:rev[a]) {
                    if (curr.first!=b) {
                        rev[b].insert(curr);
                        adj[curr.second].erase(a);
                        adj[curr.second].insert(b);
                    }
                }
                merge(b,a);
            }
            auto iter=rev[a].lower_bound(P(b,-1));
            while (iter!=rev[a].end()) {
                if ((*iter).first!=b) {
                    break;
                }
                adj[(*iter).second].erase(a);
                iter++;
                rev[a].erase(prev(iter));
            }
            auto iter2=rev[b].lower_bound(P(a,-1));
            while (iter2!=rev[b].end()) {
                if ((*iter2).first!=a) {
                    break;
                }
                adj[(*iter2).second].erase(b);
                iter2++;
                rev[b].erase(prev(iter2));
            }
        }
        printf("%lld\n",ret);
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83