제출 #446357

#제출 시각아이디문제언어결과실행 시간메모리
446357ics0503별자리 3 (JOI20_constellation3)C++17
100 / 100
1250 ms439516 KiB
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; long long a[212121]; struct xy { long long t,x,y,c; }all[414141]; long long an; bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y > b.y; if (a.t != b.t)return a.t < b.t; return a.x < b.x; } set<pair<pair<long long, long long>, long long>>S; long long tn; vector<long long>edge[414141]; vector<pair<long long, long long>>qr[414141]; long long S_start[414141], S_end[414141]; vector<long long>S_ER[414141]; long long point[414141]; void insert_S(long long s, long long e,long long parent) { tn++; S.insert({ { -s,e },tn }); S_start[tn] = s; S_end[tn] = e; if (parent) edge[parent].push_back(tn); } int pp[414141][20]; long long sparse[414141][20];; vector<int>need_to_fill[414141][20]; void init_sparse(long long w, long long bef) { pp[w][0] = bef; for (long long i = 0; pp[w][i] != -1; i++) { need_to_fill[pp[w][i]][i].push_back(w); pp[w][i + 1] = pp[pp[w][i]][i]; } for (long long nxt : edge[w]) init_sparse(nxt, w); } long long D[414141], depth[414141], CS[414141]; void dfs(long long w,long long bef,long long dep) { long long sum = 0; depth[w] = dep; for (long long nxt : edge[w]) { dfs(nxt, w, dep + 1); sum += D[nxt]; } CS[w] = sum; for (long long nxt : edge[w]) { long long v = sum - D[nxt]; sparse[nxt][0] = v; for (long long i = 1; i < 20; i++) { for (long long who : need_to_fill[nxt][i]) { long long p = pp[who][i - 1]; sparse[who][i] = sparse[p][i - 1] + sparse[who][i - 1]; } } } long long qmax = 0; for (auto q : qr[w]) { long long res = q.second; long long now = point[q.first]; res += CS[now]; for (long long i = 19; i >= 0; i--) { long long nxt = pp[now][i]; if (nxt == -1 || depth[nxt] <= depth[w])continue; res += sparse[now][i]; now = nxt; } if(now!=w)res += sparse[now][0]; qmax = max(qmax, res); } D[w] = max(sum, qmax); } int main() { long long n; scanf("%lld", &n); long long i, j; for (i = 1; i <= n; i++) { scanf("%lld", &a[i]); all[an++] = { 1,i,a[i],0 }; } long long m; scanf("%lld", &m); long long allS = 0; for (i = 1; i <= m; i++) { all[an].t = 2; scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c); allS += all[an].c; an++; } sort(all, all + an, sort_y); long long st, en; insert_S(1, n, 0); long long e9 = 1e9; for (st = 0; st < an; st = en) { for (en = st; all[st].y == all[en].y; en++); // [st, en) set<long long>erL; for (i = st; i < en; i++) { long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c; if (t != 1) continue; auto v = S.lower_bound({ { -x,-e9 },-e9 }); long long who = v->second; S_ER[who].push_back(x); erL.insert(who); } for (auto who : erL) { long long s = S_start[who], e = S_end[who]; for (i = 0; i < S_ER[who].size(); i++) { long long x = S_ER[who][i]; point[x] = who; long long new_st = s, new_en = x - 1; if (new_st <= new_en) insert_S(new_st, new_en, who); s = x + 1; if (i + 1 == S_ER[who].size()) { if (s <= e) insert_S(s, e, who); } } S.erase({ {-S_start[who],S_end[who] },who }); } for (i = st; i < en; i++) { long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c; if (t != 2) continue; auto v = S.lower_bound({ { -x,-e9 },-e9 }); if (v == S.end())continue; long long who = v->second; if(S_start[who] <= x && x <= S_end[who]) qr[who].push_back({ x, c }); } } for (i = 1; i <= tn; i++)for (j = 0; j < 20; j++)pp[i][j] = -1; init_sparse(1, -1); dfs(1, -1, 0); printf("%lld\n", allS - D[1]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:96:42: warning: unused variable 'y' [-Wunused-variable]
   96 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                          ^
constellation3.cpp:96:56: warning: unused variable 'c' [-Wunused-variable]
   96 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                                        ^
constellation3.cpp:105:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (i = 0; i < S_ER[who].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~
constellation3.cpp:111:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     if (i + 1 == S_ER[who].size()) {
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:118:42: warning: unused variable 'y' [-Wunused-variable]
  118 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                          ^
constellation3.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  long long n; scanf("%lld", &n);
      |               ~~~~~^~~~~~~~~~~~
constellation3.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
constellation3.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  long long m; scanf("%lld", &m);
      |               ~~~~~^~~~~~~~~~~~
constellation3.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...