oj.uz

Submission #212759

# Submission time Handle Problem Language Result Execution time Memory
212759 2020-03-24T09:03:32 Z Alexa2001 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 1326 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
const int Nmax = 1e5 + 5;

set<int> in[Nmax], cIn[Nmax], cOut[Nmax];

vector<int> who[Nmax];

int n, m;
int where[Nmax];

ll ans = 0;


ll take2(int x)
{
    return (ll) x * (x-1);
}


void unite(int x, int y)
{
    if(x == y) return;

    if(cIn[x].find(y) == cIn[x].end() || cOut[x].find(y) == cOut[x].end()) return;

    if(who[x].size() + in[x].size() + cIn[x].size() + cOut[x].size() < who[y].size() + in[y].size() + cIn[y].size())
        swap(x, y);

    ans -= take2(who[x].size());
    ans -= take2(who[y].size());
    ans += take2(who[x].size() + who[y].size());

    ans -= (ll) who[x].size() * in[x].size();
    ans -= (ll) who[y].size() * in[y].size();

 //   for(auto it : in[x]) cerr << it << ' '; cerr << "#\n";
  //  for(auto it : in[y]) cerr << it << ' '; cerr << "#\n";

    for(auto it : who[y])
        if(in[x].find(it) != in[x].end())
            in[x].erase(it);

    for(auto it : in[y])
        if(where[it] != x)
            in[x].insert(it);

    for(auto it : who[y])
    {
        who[x].push_back(it);
        where[it] = x;
    }

    for(auto it : cOut[y])
        if(it != x)
        {
            cIn[it].erase(y);
            cIn[it].insert(x);
            cOut[x].insert(it);
        }

    for(auto it : cIn[y])
        if(it != x)
        {
            cOut[it].erase(y);
            cOut[it].insert(y);
            cIn[x].insert(it);
        }

    ans += (ll) who[x].size() * in[x].size();

    for(auto it : cIn[y])
        unite(x, it);

    for(auto it : cOut[y])
        unite(x, it);

    who[y].clear(); in[y].clear(); cIn[y].clear(); cOut[y].clear();
}

void compute(int X, int Y)
{
    int x, y;

    x = where[X];
    y = where[Y];
    if(x == y) return;

    auto itt = in[y].insert(X);
    if(itt.second)
    {
        ans += who[y].size();
        cIn[y].insert(x);
        cOut[x].insert(y);
    }

    unite(x, y);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    for(int i=1; i<=n; ++i)
    {
        where[i] = i;
        who[i].push_back(i);
    }

    for(int i=1; i<=m; ++i)
    {
        int x, y;
        cin >> x >> y;
        compute(x, y);
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 14 ms 16640 KB Output is correct
4 Correct 13 ms 16768 KB Output is correct
5 Runtime error 1326 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 14 ms 16640 KB Output is correct
4 Correct 13 ms 16768 KB Output is correct
5 Runtime error 1326 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 14 ms 16640 KB Output is correct
4 Correct 13 ms 16768 KB Output is correct
5 Runtime error 1326 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -