Submission #56427

#TimeUsernameProblemLanguageResultExecution timeMemory
56427ics0503Construction of Highway (JOI18_construction)C++17
0 / 100
4 ms3192 KiB
#include<stdio.h> #include<vector> using namespace std; int par[121212][20], num[121212], S[121212], E[121212], cnt, tn, depth[121212];; vector<int>edge[121212]; struct xy { int x, y; }tree[313131]; xy max(xy a, xy b) { if (a.x > b.x)return a; return b; } void insert_g(int w, xy g) {for (int i = w + tn; i > 0; i /= 2)tree[i] = max(tree[i], g);} int search_g(int s, int e) { s += tn; e += tn; xy res; while (s <= e) { if ((s & 1))res = max(res, tree[s++]); if ((e & 1)== 0)res = max(res, tree[e--]); s /= 2; e /= 2; } return res.y; } void dfs(int w,int bef,int dep) { par[w][0] = bef; depth[w] = dep; for (int i = 0; par[w][i] != -1; i++)par[w][i + 1] = par[par[w][i]][i]; num[w] = S[w] = ++cnt; for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) { dfs(edge[w][i], w, dep+1); } E[w] = cnt; } int get_C(int x) { return search_g(S[x], E[x]); } int A[121212],B[121212]; int C[121212], CSD[121212]; int go(int a, int b) { for (int i = 0; i < 20; i++)if ((1 << i)&b)a = par[a][i]; return a; } vector<xy>L; xy temp[121212]; long long f(int s, int e) { if (s == e)return 0; int m = (s + e) / 2, i; long long res = f(s, m) + f(m + 1, e); int p1 = s, p2 = m + 1; int jw = m, S = 0; for (i = s; i <= m; i++) { while (jw + 1 <= e&&L[i].x < L[jw + 1].x)S += L[++jw].y; res += (long long)L[i].y * S; } for (i = s; i <= e; i++) { if (p1 == m + 1 || (p2 != e + 1 && L[p1].x < L[p2].x)) temp[i] = L[p2++]; else temp[i] = L[p1++]; } for (i = s; i <= e; i++) L[i] = temp[i]; return res; } int main() { int n; scanf("%d", &n); int i, j; for (tn = 1; tn < n + 1; tn *= 2); for (i = 0; i < tn * 2; i++)tree[i].x = -1; for (i = 1; i <= n; i++)scanf("%d", &C[i]); for (i = 1; i <= n; i++)for (j = 0; j < 20; j++)par[i][j] = -1; for (i = 1; i <= n - 1; i++) { int s, e; scanf("%d%d", &s, &e); A[i] = s; B[i] = e; edge[s].push_back(e); edge[e].push_back(s); } dfs(1, -1, 0); CSD[1] = 0; insert_g(1, { 0,1 }); int SS = 0; for (i = 1; i <= n - 1; i++) { L.clear(); int e = B[i], now = par[e][0]; while (now != -1) { int nowC = get_C(now); int cs = go(now, depth[now] - CSD[nowC]); L.push_back({ C[nowC], depth[now] - CSD[nowC] + 1 }); CSD[nowC] = depth[now] + 1; now = par[cs][0]; } insert_g(num[e], { i, e }); printf("%lld\n", f(0, L.size() - 1)); } return 0; }

Compilation message (stderr)

construction.cpp: In function 'void dfs(int, int, int)':
construction.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edge[w].size(); i++)if (edge[w][i] != bef) {
                  ~~^~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:64:6: warning: unused variable 'SS' [-Wunused-variable]
  int SS = 0;
      ^~
construction.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
construction.cpp:55:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &C[i]);
                          ~~~~~^~~~~~~~~~~~~
construction.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...