oj.uz

답안 #406824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406824 2021-05-18T05:44:06 Z urd05 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 5000 ms 10064 KB 
#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(b);
            rev[b].insert(P(find(a),a));
            edge.insert(P(a,b));
            ret+=-p[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()-1>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);
                rev[a].erase(iter);
                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);
                rev[b].erase(iter2);
                iter2++;
            }
        }
        printf("%lld\n",ret);
    }
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5016 ms 10064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5016 ms 10064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5016 ms 10064 KB Time limit exceeded
2 Halted 0 ms 0 KB -