Submission #138132

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
138132	2019-07-29 11:56:09	Mahmoud_Adel	Mergers (JOI19_mergers)	C++14	70 / 100	799 ms	99080 KiB

mergers

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;
#define f first
#define s second
typedef long long ll;
const int N = 5e5+5;
int n, m, ans, cur, s[N], dep[N], sp[N][20], sub[N], ret[N], mark[N], deg[N];
vector<int> adj[N], vec[N];
void pre(int u, int p)
{
  sub[u] = 1;
  dep[u] = dep[p]+1;
  sp[u][0] = p;
  for(int i=1; i<20; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
  for(int v : adj[u]) if(v != p) pre(v, u), sub[u] += sub[v]; 
} 
int equate(int u, int v)
{
  int c = dep[u]-dep[v];
  for(int i=0; i<20; i++) if(c & (1<<i)) u = sp[u][i];
  return u;
}
int LCA(int u, int v)
{
  if(dep[u] < dep[v]) swap(u, v);
  u = equate(u, v);
  if(u == v) return u;
  for(int i=19; i>=0; i--) if(sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
  return sp[u][0];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:49:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1, a, b; i<n; i++) scanf("%d %d", &a, &b),
                               ~~~~~~~~~~~~~~~~~~~~~~~~
  adj[a].push_back(b), adj[b].push_back(a);
  ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
mergers.cpp:50:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &s[i]), vec[s[i]].push_back(i);
                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 0 / 30