Submission #204083

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
204083	2020-02-24 09:40:57	ics0503	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	769 ms	84456 KiB

designated_cities

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<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121], F[212121], FW[212121];
void get_DF(long long w,long long bef) {
  D[w] = F[w] = 0; FW[w] = w;
  for (xy E : edge[w]) if (E.x != bef) {
    get_DF(E.x, w);
    D[w] += D[E.x] + E.y;
    if (F[w] < F[E.x] + E.z) {
      F[w] = F[E.x] + E.z;
      FW[w] = FW[E.x];
    }
  }
}
long long resX[212121], resY[212121], l[212121], r[212121];
void get_res(long long w, long long bef, long long fromRoot) {
  long long sum = 0, cnt = 0;
  vector<pair<long long, long long>>L;
  for (xy E : edge[w]) if (E.x != bef) {
    sum += D[E.x] + E.y;
    L.push_back({ -(F[E.x] + E.z), FW[E.x] });
  }
  sort(L.begin(), L.end());
  resX[w] = sum + fromRoot;
  if (L.size() > 0)resY[w] = -(L[0].first) + sum + fromRoot, l[w] = w, r[w] = L[0].second;
  if (L.size() > 1)resY[w] = -(L[0].first + L[1].first) + sum + fromRoot, l[w] = L[0].second, r[w] = L[1].second;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

designated_cities.cpp: In function 'void get_res(long long int, long long int, long long int)':
designated_cities.cpp:21:21: warning: unused variable 'cnt' [-Wunused-variable]
  long long sum = 0, cnt = 0;
                     ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:85:16: warning: unused variable 'j' [-Wunused-variable]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                ^
designated_cities.cpp:85:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                               ~~~~~^~~~~~~~~~~~
designated_cities.cpp:87:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long q, x; scanf("%lld", &q);
                  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44