제출 #878400

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
878400	2023-11-24 10:01:43	amirhoseinfar1385	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	375 ms	43088 KiB

joitter2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m; 
struct dsu{
  int par[maxn],sz[maxn];
  set<pair<int,int>>kho[maxn];
  set<int>vorod[maxn];
  long long res;
  dsu(){
    res=0;
    for(int i=1;i<maxn;i++){
      par[i]=i;
      sz[i]=1;
    }
  }
  int root(int u){
    if(u==par[u])return u;
    return par[u]=root(par[u]);
  }
  void con(int u,int v){
    u=root(u),v=root(v);
    if(sz[u]>sz[v])swap(u,v);
    vector<pair<int,int>>allq;
    for(auto x:kho[u]){
      res-=sz[x.first];
      vorod[x.first].erase(x.second);
      allq.push_back(make_pair(x.second,x.first));
    }
    res+=sz[u]*(2*sz[v]+vorod[v].size());
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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