oj.uz

Submission #269153

# Submission time Handle Problem Language Result Execution time Memory
269153 2020-08-17T05:28:21 Z 최은수(#5097) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 11 ms 12032 KB 
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int par[100010];
vector<int>gv[100010];
int sz[100010];
set<int>rev[100010];
map<int,int>cnt[100010];
ll ans;
inline void uni(int x,int y)
{
    x=par[x];
    y=par[y];
    if(x==y)
        return;
    if(sz[x]>sz[y])
        swap(x,y);
    vector<int>putv;
    ans-=(ll)cnt[x][y]*sz[y]+(ll)cnt[y][x]*sz[x];
    ans+=(ll)sz[x]*sz[y]*2;
    ans+=sz[x]*((ll)rev[y].size()-cnt[y][y]);
    for(int t:rev[x])
    {
        if(par[t]==y)
            ans-=sz[x];
        else if(rev[y].find(t)==rev[y].end())
            putv.eb(t);
        else
            ans-=sz[x];
    }
    for(int&t:putv)
    {
        rev[y].ep(t);
        cnt[par[t]][y]++;
        ans+=sz[y];
    }
    cnt[y][y]+=cnt[x][y];
    sz[y]+=sz[x];
    for(int&t:gv[x])
        par[t]=y,gv[y].eb(t);
    gv[x].clear();
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i++<n;)
        gv[par[i]=i].eb(i),sz[i]=1;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(par[u]!=par[v]&&rev[par[v]].find(u)==rev[par[v]].end())
        {
            ans+=sz[par[v]];
            rev[par[v]].ep(u);
            cnt[par[u]][par[v]]++;
            if(cnt[par[v]][par[u]]>0)
                uni(par[u],par[v]);
        }
        cout<<ans<<'\n';
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Incorrect 8 ms 12032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Incorrect 8 ms 12032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Incorrect 8 ms 12032 KB Output isn't correct
4 Halted 0 ms 0 KB -