oj.uz

답안 #359106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359106 2021-01-26T11:01:32 Z Nima_Naderi 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 52 ms 75500 KB 
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 4e5 + 10;
ll n, m, ans, pnt;
ll Par[MXN], Sz[MXN];
set<ll> In[MXN], Out[MXN], To[MXN], Comp[MXN];
vector<pair<ll, ll>> Q;
ll Find(ll x){
    return (x == Par[x] ? x : Par[x] = Find(Par[x]));
}
void add(ll u, ll v){
    if(u == v) return;
    Out[u].insert(v), In[v].insert(u);
    if(In[u].find(v) != In[u].end()) Q.push_back({u, v});
}
void Union(ll x, ll y){
    x = Find(x), y = Find(y);
    if(x == y) return;
    if(Sz[x] < Sz[y]) swap(x, y);
    /*
    cout << "====================\n";
    cout << x << ' ' << y << '\n';
    cout << ans << '\n';
    cout << To[x].size() << '\n';
    cout << To[y].size() << '\n';
    cout << "====================\n";
    */
    ans -= Sz[x] * (Sz[x] - 1);
    ans -= Sz[y] * (Sz[y] - 1);
    ans -= 1ll * To[x].size() * (Sz[x]);
    ans -= 1ll * To[y].size() * (Sz[y]);

    for(auto X : In[y])  Out[X].erase(y);
    for(auto X : Out[y]) In[X].erase(y);
    for(auto X : In[y])  add(X, x);
    for(auto X : Out[y]) add(x, X);
    for(auto X : Comp[y]){
        auto itr = To[x].find(X);
        if(itr == To[x].end()) continue;
        To[x].erase(itr);
    }
    for(auto X : To[y]){
        if(Find(X) != x){
            To[x].insert(X);
        }
    }
    In[y].clear(), Out[y].clear(), To[y].clear();
    Sz[x] += Sz[y], Par[y] = x;
    ans += 1ll * To[x].size() * (Sz[x]);
    ans += Sz[x] * (Sz[x] - 1);
    for(auto X : Comp[y]) Comp[x].insert(X);
    Comp[y].clear();
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) Par[i] = i, Sz[i] = 1, Comp[i].insert(i);
    for(int i = 1; i <= m; i ++){
        ll u, v; cin >> u >> v;
        if(Find(u) == Find(v) || To[Find(v)].find(u) != To[Find(v)].end()){
            cout << ans << '\n';
            continue;
        }
        To[Find(v)].insert(u), ans += Sz[v];
        add(Find(u), Find(v));
        while(pnt < Q.size()){
            ll x, y; tie(x, y) = Q[pnt];
            pnt ++;
            Union(x, y);
        }
        cout << ans << '\n';
    }
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:70:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while(pnt < Q.size()){
      |               ~~~~^~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 75500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 75500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 75500 KB Output isn't correct
2 Halted 0 ms 0 KB -