Submission #259786

#	Time	Username	Problem	Language	Result	Execution time	Memory
259786		Kastanda	Making Friends on Joitter is Fun (JOI20_joitter2)	C++11	100 / 100	1545 ms	92424 KiB

joitter2

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, P[N];
long long tot;
set < int > In[N], Out[N], Fin[N];
set < pair < int , int > > Fout[N];
vector < pair < int , int > > Edges[N];
queue < pair < int , int > > E;
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        if (Edges[v].size() < Edges[u].size())
                swap(v, u);

        //printf("%d :::: %d\n", v, u);
        tot -= (-P[u]) * 1LL * (int)Fin[u].size();
        tot += (-P[u]) * 1LL * (int)Fin[v].size();
        for (int a : Fin[u])
                Fout[Find(a)].erase({u, a});
        Fin[u].clear();
        for (auto a : Fout[u])
        {
                tot -= -P[a.first];
                Fin[a.first].erase(a.second);
                if (a.first == v)
                        tot -= -P[u];
        }
        Fout[u].clear();

        for (auto X : Edges[u])
                E.push(X);//, printf("%d , %d\n", X.first, X.second), fflush(stdout);
        Edges[u].clear();

        In[u].clear();
        Out[u].clear();

        tot += P[v] * 2LL * P[u];
        P[v] += P[u];
        P[u] = v;
}
int main()
{
        scanf("%d%d", &n, &m);
        memset(P, -1, sizeof(P));
        for (int i = 1; i <= m; i ++)
        {
                int a, b;
                scanf("%d%d", &a, &b);
                E.push({a, b});
                /*if (i >= 6)
                        printf("%d =====\n", i);
                fflush(stdout);*/
                while (E.size())
                {
                        /*if (i == 7)
                                printf("|| %lld  ||\n", tot);*/
                        int v = E.front().first;
                        int u = E.front().second;
                        E.pop();
                        int pv = Find(v);
                        int pu = Find(u);
                        if (pv == pu)
                                continue;
                        if (!Out[pu].count(pv))
                        {
                                if (Fout[pv].count({pu, v}))
                                        continue;
                                Edges[pv].push_back(make_pair(v, u));
                                Edges[pu].push_back(make_pair(v, u));
                                Fout[pv].insert({pu, v});
                                Fin[pu].insert(v);
                                Out[pv].insert(pu);
                                In[pu].insert(pv);
                                tot += -P[pu];
                                continue;
                        }
                        Merge(pv, pu);
                }
                printf("%lld\n", tot);
        }
        return 0;
}

Compilation message (stderr)

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

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