Submission #943286

#TimeUsernameProblemLanguageResultExecution timeMemory
943286lovrotConstruction of Highway (JOI18_construction)C++17
16 / 100
2078 ms28316 KiB
#include <cstdio> #include <set> #include <vector> #include <algorithm> #include <stack> #define X first #define Y second #define PB push_back #define MP make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; const int LOG = 17; const int N = 1 << LOG; struct fenwick { int F[N]; stack<pii> U; fenwick() { for(int &x : F) x = 0; } void add(int x, int val, bool f = 1) { if(f) U.push({x, val}); for(; x < N; x += x & -x) F[x] += val; } int sum(int x) { int ret = 0; for(; x; x -= x & -x) ret += F[x]; return ret; } void clear() { for(; !U.empty(); U.pop()) add(U.top().X, -U.top().Y, 0); } }; int A[N], B[N], C[N]; int DEP[N], SIZ[N], CH[N], chi, H[N], P[N]; vector<int> G[N], CMP; int dfs(int u) { ++SIZ[u]; int mx = 0, mxi = 0; for(int v : G[u]) { DEP[v] = DEP[u] + 1; int res = dfs(v); SIZ[u] += res; if(res > mx) { mx = res; mxi = v; } } CH[u] = !mxi ? ++chi : CH[mxi]; H[CH[u]] = u; return SIZ[u]; } fenwick F; set<pii> S[N]; // {DEP, VAL} ll solve(int u, int x) { // NE ZABORAVI parent mora bit dodan u set od lanca (1 !!!) if(!u) { F.clear(); return 0; } // printf("entry %d\n", u); int ch = CH[u]; auto it = S[ch].lower_bound(MP(DEP[u], -1)); ll ret = 0; for(bool flag = (*it).X == DEP[u]; 1; flag = 1) { int dep = (*it).X, val = (*it).Y; int siz = dep - (it == S[ch].begin() ? DEP[H[ch]] - 1 : (*prev(it)).X); // printf("() %d %d %d\n", dep, siz, val); ret += (ll) siz * F.sum(val - 1); F.add(val, siz); auto nxt = it == S[ch].begin() ? S[ch].end() : prev(it); if(flag) S[ch].erase(it); S[ch].insert(MP(dep, x)); if(nxt == S[ch].end()) break; it = nxt; } return ret + solve(P[H[ch]], x); } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", C + i); CMP.PB(C[i]); } sort(CMP.begin(), CMP.end()); CMP.erase(unique(CMP.begin(), CMP.end()), CMP.end()); for(int i = 1; i <= n; ++i) C[i] = upper_bound(CMP.begin(), CMP.end(), C[i]) - CMP.begin(); for(int i = 0; i < n - 1; ++i) { scanf("%d%d", A + i, B + i); G[A[i]].PB(B[i]); P[B[i]] = A[i]; } dfs(1); // for(int i = 1; i <= n; ++i) printf("dep %d siz %d ch %d\n", DEP[i], SIZ[i], CH[i]); S[CH[1]].insert({DEP[1], C[1]}); for(int i = 0; i < n - 1; ++i) { S[CH[B[i]]].insert({DEP[B[i]], C[B[i]]}); printf("%lld\n", solve(A[i], C[B[i]])); } return 0; }

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
construction.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   scanf("%d", C + i);
      |   ~~~~~^~~~~~~~~~~~~
construction.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...