Submission #216728

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
216728	2020-03-27 23:47:11	ainta	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	2257 ms	121324 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<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#define N_ 101000
using namespace std;
int n, m, UF[N_];
long long res, InD[N_];
map<int, int>Out[N_], In[N_];
vector<int>G[N_];
set<int>E[N_], F[N_];
int Find(int a) {
  if (a == UF[a])return a;
  return UF[a] = Find(UF[a]);
}
void Merge(int a, int b) {
  if (Find(a) == Find(b))return;
  int pa = Find(a), pb = Find(b);
  int nd = InD[pa] + InD[pb] - Out[pb][pa] - Out[pa][pb];
  res += 1ll * (G[pa].size() + G[pb].size()) * nd + 1ll * G[pa].size()*G[pb].size() * 2;
  res -= 1ll * InD[pb] * G[pb].size();
  res -= 1ll * InD[pa] * G[pa].size();
  if (G[pa].size() + In[pa].size() + Out[pa].size() + F[pa].size() < G[pb].size() + In[pb].size() + Out[pb].size() + F[pb].size())swap(pa, pb);
  InD[pa] = nd;
  
  In[pb].erase(pa);
  Out[pb].erase(pa);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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