Submission #932764

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
932764	2024-02-24 07:18:31	WongChun1234	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	2 ms	10844 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>
#define int long long
using namespace std;
const int N=100050;
const bool DEBUG=0;
int n,m,a,b,par[N],sz[N],inord[N],ans;
map<int,int> one[N],frm[N];
int find(int u){
  return par[u]=(par[u]==u?u:find(par[u]));
}
signed main(){
  cin>>n>>m;
  iota(par+1,par+n+1,1);
  for (int i=1;i<=n;i++) sz[i]=1;
  while (m--){
    cin>>a>>b;
    if (DEBUG) cout<<a<<"->"<<b<<"\n";
    if (find(a)==find(b)||one[find(b)][a]){
        if (DEBUG) cout<<"ignore\n";
      //alr have a->b edge
    }else if (frm[find(a)][find(b)]){
      //union find(a) and find(b)
      if (DEBUG) cout<<"merge "<<find(a)<<" "<<find(b)<<"\n";
      a=find(a);
      b=find(b);
      if (DEBUG) cout<<"size "<<sz[a]<<" "<<sz[b]<<" frm "<<frm[a][b]<<"\n";
      if (DEBUG) cout<<"inord "<<inord[a]<<" "<<inord[b]<<"\n";
      ans+=sz[a]*sz[b]*2;
      ans-=sz[a]*frm[a][b];
      inord[a]-=frm[a][b];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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