Submission #382282

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
382282	2021-03-26 23:09:07	couplefire	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1099 ms	73244 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 pii pair<int, int>
#define x first
#define y second
 
using namespace std;
 
const int N = 1e5 + 10;
set<int> in[N], out[N], com[N], e[N];
long long ans;
long long par[N], sz[N];
int n, m;
 
int find( int u ) { return par[u] == u ? u : par[u] = find( par[u] ); }
 
long long cal( int u ) { return 1LL * ( ( ( int )e[u].size() - sz[u] ) * sz[u] ) + 1LL * sz[u] * ( sz[u]-1 ); }
 
void merge( int a, int b ) {
    vector<pii> v;
    a = find( a ), b = find( b );
    if( a == b ) return ;
    if( in[a].size() + out[a].size() + e[a].size() < in[b].size() + out[b].size() + e[b].size() ) swap( a, b );
    ans -= cal( a ), ans -= cal( b );
    in[a].erase( b ), in[b].erase( a ), out[a].erase( b ), out[b].erase( a );
    for( int x : in[b] ) {
        if( out[a].count( x ) ) v.emplace_back( x, a );
        out[x].erase( b ), out[x].emplace( a );
    }
    for( int x : out[b] ) {
        if( in[a].count( x ) ) v.emplace_back( x, a );
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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