oj.uz

Submission #259784

# Submission time Handle Problem Language Result Execution time Memory
259784 2020-08-08T14:20:25 Z Kastanda Making Friends on Joitter is Fun (JOI20_joitter2) C++11
0 / 100
 13 ms 21888 KB 
// 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);

        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;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:42: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:47: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 21888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 21888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 21888 KB Output isn't correct
2 Halted 0 ms 0 KB -