oj.uz

Submission #269225

# Submission time Handle Problem Language Result Execution time Memory
269225 2020-08-17T05:50:01 Z 최은수(#5097) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 10 ms 12160 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;
vector<pi>univ;
inline void uni(int x,int y)
{
    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[x][y]-cnt[y][y]);
    for(int t:rev[x])
    {
        if(par[t]==x||par[t]==y)
            continue;
        if(rev[y].find(t)==rev[y].end())
            putv.eb(t);
        else
            ans-=sz[x];
    }
    for(int&t:putv)
    {
        rev[y].ep(t);
        if(cnt[y][par[t]]>0)
            univ.eb(y,par[t]);
        cnt[par[t]][y]++;
        ans+=sz[y];
    }
    for(pi t:cnt[x])
    {
        if(t.fi==par[t.fi]&&t.se>0&&rev[y].find(t.fi)!=rev[y].end())
            univ.eb(y,t.fi);
        cnt[y][t.fi]+=t.se;
    }
    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)
            {
                univ.eb(u,v);
                while(!univ.empty())
                {
                    pi t=univ.back();
                    univ.pop_back();
                    if(par[t.fi]!=par[t.se])
                        uni(par[t.fi],par[t.se]);
                }
            }
        }
        cout<<ans<<'\n';
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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