제출 #259783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259783		Kastanda	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	0 / 100	13 ms	22016 KiB

joitter2

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, tot, P[N];
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);

        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);
        Fout[u].clear();

        for (auto X : Edges[u])
                E.push(X);
        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});
                while (E.size())
                {
                        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;
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:72:37: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
                 printf("%lld\n", tot);
                                     ^
joitter2.cpp:41: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:46: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: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83