Submission #538163

#	Time	Username	Problem	Language	Result	Execution time	Memory
538163		urd05	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	4 ms	7252 KiB

joitter2

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

set<int> rev[100001];
int in[100001];
int p[100001];
int sz[100001];
vector<int> vec[100001];

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        p[i]=i;
        vec[i].push_back(i);
        sz[i]=1;
    }
    long long ret=0;
    for(int i=0;i<m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        if (p[a]==p[b]||rev[p[b]].find(a)!=rev[p[b]].end()) {
            printf("%lld\n",ret);
            continue;
        }
        if (rev[p[a]].find(b)==rev[p[a]].end()) {
            rev[p[b]].insert(a);
            ret+=sz[p[b]];
            in[p[b]]++;
            printf("%lld\n",ret);
            continue;
        }
        a=p[a];
        b=p[b];
        if (sz[a]>sz[b]) {
            swap(a,b);
        }
        ret-=1LL*sz[a]*(sz[a]-1);
        ret-=1LL*sz[b]*(sz[b]-1);
        ret+=1LL*(sz[a]+sz[b])*(sz[a]+sz[b]-1);
        int cnt1=0;
        int cnt2=0;
        for(int i=0;i<vec[a].size();i++) {
            if (rev[b].find(vec[a][i])!=rev[b].end()) {
                rev[b].erase(vec[a][i]);
                cnt2++;
            }
        }
        vector<int> save;
        for(auto now:rev[a]) {
            if (p[now]==b) {
                cnt1++;
                save.push_back(now);
            }
        }
        for(int i=0;i<save.size();i++) {
            rev[a].erase(save[i]);
        }
        ret-=1LL*cnt1*sz[a];
        ret-=1LL*cnt2*sz[b];
        in[a]-=cnt1;
        in[b]-=cnt2;
        ret-=1LL*sz[a]*in[a]+1LL*sz[b]*in[b];
		ret+=1LL*(sz[a]+sz[b])*in[b];
        for(auto now:rev[a]) {
            if (rev[b].find(now)==rev[b].end()) {
                rev[b].insert(now);
                ret+=sz[a]+sz[b];
                in[b]++;
            }
        }
        for(int i=0;i<vec[a].size();i++) {
            vec[b].push_back(vec[a][i]);
            p[vec[a][i]]=b;
        }
        sz[b]+=sz[a];
        printf("%lld\n",ret);
    }
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i=0;i<vec[a].size();i++) {
      |                     ~^~~~~~~~~~~~~~
joitter2.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=0;i<save.size();i++) {
      |                     ~^~~~~~~~~~~~
joitter2.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=0;i<vec[a].size();i++) {
      |                     ~^~~~~~~~~~~~~~
joitter2.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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