Submission #216732

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
216732	2020-03-27 23:50:37	ainta	Capital City (JOI20_capital_city)	C++17	100 / 100	962 ms	174600 KiB

capital_city

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<vector>
#define N_ 210000
#define M_ 1010000
using namespace std;
vector<int>E[N_], G[M_], P[N_], H[M_];
int n, w[N_], K, C[N_], Dep[N_], par[N_][20], PPP[N_], Num[N_], Ed[N_], ReNum[N_], cnt;
void DFS(int a, int pp) {
  par[a][0] = pp;
  C[a] = 1;
  for (int i = 0; i < 18; i++)par[a][i + 1] = par[par[a][i]][i];
  for (auto &x : E[a]) {
    if (x != pp) {
      Dep[x] = Dep[a] + 1;
      DFS(x, a);
      C[a] += C[x];
    }
  }
}
void HLD(int a, int pp, int rt) {
  Num[a] = ++cnt;
  ReNum[cnt] = a;
  G[n + cnt].push_back(w[a]);
  PPP[a] = rt;
  int Mx = -1, pv = -1;
  for (auto &x : E[a]) {
    if (x == pp)continue;
    if (Mx < C[x])Mx = C[x], pv = x;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n,&K);
  ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59