제출 #233199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233199		medk	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	컴파일 에러	0 ms	0 KiB

joitter2

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (long long)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

const int MAXN=1e5;
int n,m;
ll ans=0;

map<int,set<int>> in[MAXN],out[MAXN];
set<int> in2[MAXN],out2[MAXN];
vector<ll> dsu,sz,acc(MAXN);


//in : **node** -> this group
//out : this node -> **group**
//in2 : **group** -> this group
//out2: this group -> **group**

int getp(int u)
{
    if(dsu[u]==u) return u;
    return dsu[u]=getp(dsu[u]);
}

void connect(int u, int v)
{
    u=getp(u), v=getp(v);
    if(u==v) return;
    if(acc[v]>acc[u]) swap(u,v);
    ans-=sz[u]*(sz[u]-1);
    ans-=sz[v]*(sz[v]-1);
    ans+=(sz[u]+sz[v])*(sz[u]+sz[v]-1);
    in2[u].erase(v);
    out2[u].erase(v);
    in2[v].erase(u);
    out2[v].erase(u);
    vector<int> qu;
    acc[u]-=sz(in[u][v]);
    ans+=acc[u]*sz[v];
    for(int w:in2[v])
    {
        if(getp(w)==u) continue;
        in2[u].insert(w);
        out2[w].erase(v);
        out2[w].insert(u);
        for(int z:in[v][w])
            if(!in[u][w].count(z)) {in[u][w].insert(z), ans+=sz[u], acc[u]++;} out[w][u].insert(z);
    }
    for(int w:out2[v])
    {
        out2[u].insert(w);
        in2[w].erase(v);
        in2[w].insert(u);
        if(in2[u].count(w)) qu.pb(w);
        for(int z:out[v][w])
            out[u][w].insert(z), in[w][u].insert(z);
    }
    for(int w:in2[v])
        if(w!=u) if(out2[u].count(w)) qu.pb(w);
    ans-=sz(in[v][u])*sz[v]+sz(in[u][v])*sz[u];
    sz[u]+=sz[v];
    dsu[v]=u;
    for(int q:qu) connect(u,q);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) dsu.pb(i), sz.pb(1);
    for(int i=0;i<m;i++)
    {
        int u,v; cin>>u>>v;
        u--,v--;
        int paru=getp(u), parv=getp(v);
        if(paru==parv || in[parv][paru].count(u))
        {
            cout<<ans<<'\n';
            continue;
        }
        if(in2[paru].count(parv))
        {
            connect(paru,parv);
            cout<<ans<<'\n';
            continue;
        }
        in2[parv].insert(paru);
        out2[paru].insert(parv);
        in[parv][paru].insert(u), acc[parv]++;
        out[paru][parv].insert(u);
        ans+=sz[parv];
        cout<<ans<<'\n';
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'void connect(int, int)':
joitter2.cpp:53:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(int z:in[v][w])
         ^~~
joitter2.cpp:54:80: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             if(!in[u][w].count(z)) {in[u][w].insert(z), ans+=sz[u], acc[u]++;} out[w][u].insert(z);
                                                                                ^~~
joitter2.cpp:54:97: error: 'z' was not declared in this scope
             if(!in[u][w].count(z)) {in[u][w].insert(z), ans+=sz[u], acc[u]++;} out[w][u].insert(z);
                                                                                                 ^