oj.uz

답안 #961793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961793 2024-04-12T12:56:42 Z danikoynov 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 1 ms 724 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 2010;

int n, par[maxn], m;
int sz[maxn];

int find_leader(int v)
{
    if (par[v] == v)
        return v;
    return (par[v] = find_leader(par[v]));
}


set < int > rem;
set < int > in_adj_diff[maxn];
set < int > in_adj[maxn], out_adj[maxn];

ll calc(int v)
{
///cout << "calc " << v << " " << sz[v] << " " << in_adj_diff[v].size() << endl;
   // for (int w : in_adj_diff[v])cout << w << " ";
     //cout << endl;
    ll s = sz[v];
    return s * (s - 1 + (ll)(in_adj_diff[v].size()));
}

ll res;
void unite(int v, int u)
{

    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return;
    ///cout << "unite " << v << " " << u << endl;
    if (rem.find(v) == rem.end())
    {
        res = res - calc(v);
        rem.insert(v);
    }
    if (rem.find(u) == rem.end())
    {
        res = res - calc(u);
        rem.insert(u);
     }


    vector < int > d;

    for (int w : out_adj[u])
    {
        if (find_leader(w) == v)
            continue;
        out_adj[v].insert(w);

        if (in_adj_diff[v].find(find_leader(w)) != in_adj_diff[v].end())
          {
               //cout << "PUSH TO D " << w << endl;
               d.push_back(w);
          }
    }


    for (int w : in_adj_diff[u])
    {
        if (find_leader(w) == v)
            continue;
            ///cout << "to " << v << " " << w << endl;
        in_adj_diff[v].insert(w);
        if (out_adj[v].find(find_leader(w)) != out_adj[v].end())
            d.push_back(w);
    }

        par[u] = v;
    sz[v] += sz[u];

     in_adj_diff[u].clear();
     out_adj[u].clear();

    vector < int > sd;
    for (int k : in_adj_diff[v])
    {
         ///cout << v << " : " << k << " " << endl;
         if (find_leader(k) == v)

          sd.push_back(k);
    }
    for (int k : sd)
     in_adj_diff[v].erase(k);

    for (int c : d)
        unite(v, c);
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        par[i] = i;
        sz[i] = 1;
    }

    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        int lv = find_leader(v);
        int lu = find_leader(u);
        if (lv == lu)
        {
            cout << res << endl;
            continue;
        }
        if (in_adj_diff[lv].find(lu) != in_adj_diff[lv].end())
        {
            rem.clear();
            unite(lv, lu);
            set < int > st;
            for (int c : rem)
                st.insert(find_leader(c));

            for (int c : st)
               {
                    ///cout << "recalc " << c << endl;
                    res += calc(c);
               }
        }
        else
        {
            res = res - calc(lv);
            res = res - calc(lu);
            out_adj[lv].insert(lu);
            in_adj[lu].insert(lv);
            in_adj_diff[lu].insert(v);
            res = res + calc(lv);
            res = res + calc(lu);
        }

       cout  << res << endl;
          /**cout << "--------------------" << endl;
          for (int i = 1; i <= n; i ++)
          {
               cout << "vertex " << i << endl;
               for (int u : in_adj_diff[i])
                    cout << u << " ";
               cout << endl;
          }
          cout << "|||||" << endl;*/
    }
}

int main()
{
    solve();
    return 0;
}
/**
5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2

5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3


4 3
1 2
2 3
3 2


*/

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 704 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 704 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 704 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -