제출 #1348909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1348909		kokokai	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	2 ms	5452 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "text"
const int N = 1e5+5;
int lab[N];
ll ans;
map<int,bool> conto[N];
int findpar(int u){
    if(lab[u]<0) return u;
    return lab[u]=findpar(lab[u]);
}
int siz(int a){
    a=findpar(a);
    return -lab[a];
}
void unite(int u,int v){
    u=findpar(u);
    v=findpar(v);
    if(u == v) return;
    ans += siz(u) * siz(v) * 2;
    ans += siz(v) * conto[u].size();
    //cerr<<u<<' '<<v<<' '<<conto[v].size()<<'\n';
    ans += siz(u) * conto[v].size();
    if(conto[u].size() < conto[v].size()) swap(u,v);
    for(auto x:conto[v]){
        conto[u][x.fi]=1;
    }
    conto[v].clear();
    lab[u] += lab[v];
    lab[v] = u;
}
int n,m;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m;
    memset(lab,-1,sizeof lab);
    for(int t=1;t<=m;t++){
        int a,b;
        cin>>a>>b;
        if(findpar(a) == findpar(b)){
            cout<<ans<<'\n';
            continue;
        }
        int pa=findpar(a);
        if(conto[pa].find(b) != conto[pa].end()){
            ans -= siz(pa);
            //cerr<<ans<<'\n';
            conto[pa].erase(b);
            unite(pa,b);

            cout<<ans<<'\n';
            continue;
        }
        int pb=findpar(b);
        if(conto[pb].find(a) == conto[pb].end()){

            conto[pb][a]=1;
            //cerr<<pb<<' '<<a<<' '<<conto[2].size()<<'\n';
            ans += siz(pb);
        }

        cout<<ans<<'\n';
    }
}

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

joitter2.cpp: In function 'int main()':
joitter2.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83