Submission #827379

#TimeUsernameProblemLanguageResultExecution timeMemory
827379lovrotTourism (JOI23_tourism)C++17
100 / 100
618 ms27592 KiB
#include <bits/stdc++.h> #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; int abs(int x) { if(x < 0) return -x; return x; } const int LOG = 17; const int OFF = 1 << LOG; const int INF = 1e9; struct intv { int l, r, val; bool op; intv (int l, int r, int val) : l(l), r(r), val(val) { op = 0; } intv (int l, int r, int val, int op) : l(l), r(r), val(val), op(op) {} bool operator< (intv a) const { return l < a.l || (l == a.l && r < a.r); } }; int CNT; int head[OFF], heav[OFF], pos[OFF], par[OFF], dep[OFF]; vector<int> g[OFF]; vector<intv> ups; int dfs(int u) { int siz = 1, maxs = 0, ind = 0; for(int v : g[u]) { if(v == par[u]) continue; par[v] = u, dep[v] = dep[u] + 1; int res = dfs(v); if(res > maxs) maxs = res, ind = v; siz += res; } heav[u] = ind; // printf("%d -> %d\n", u, ind); return siz; } void decomp(int u, int h) { pos[u] = CNT++, head[u] = h; // printf("%d[%d, %d]\n", u, pos[u], head[u]); if(heav[u] && u != 1) decomp(heav[u], h); for(int v : g[u]) { if(v == par[u] || v == heav[u] && u != 1) continue; decomp(v, v); } } int fen[OFF]; set<intv> s; void add(int x, int val) { for(x; x < OFF; x += x & -x) fen[x] += val; } int sum(int x) { int ret = 0; for(x; x; x -= x & -x) ret += fen[x]; return ret; } void change(intv i) { // if(i.op) printf("%d %d -%d\n", i.l, i.r, i.val); // else printf("%d %d %d\n", i.l, i.r, i.val); int val = i.r - i.l + 1; if(i.op) val = -val; add(i.val + 1, val); } void debug() { for(auto it : s) { printf("[%d, %d (%d)] ", it.l, it.r, it.val); } printf("\n"); } //shit void interval(int l, int r, int val) { if(l > r) return; ups.clear(); ups.pb(intv(l, r, val)); auto it = prev(s.upper_bound(intv(l, INF, INF))); if(it->l < l) ups.pb(intv(it->l, l - 1, it->val)); while(it != s.end() && it->l <= r) { if(it->r > r) ups.pb(intv(r + 1, it->r, it->val)); auto nit = next(it); change(intv(it->l, it->r, it->val, 1)); s.erase(it); it = nit; } for(intv p : ups) { s.insert(p); change(p); } //printf("add %d %d %d\n", l, r, val); // debug(); } void update(int u, int v, int val) { for(; head[u] != head[v]; v = par[head[v]]) { if(dep[head[u]] > dep[head[v]]) swap(u, v); interval(pos[head[v]], pos[v], val); } if(dep[u] > dep[v]) swap(u, v); interval(pos[u] + 1, pos[v], val); } int n, m, t, ans[OFF]; vector<int> c; vector<pii> q[OFF]; int main() { scanf("%d%d%d", &n, &m, &t); for(int i = 0; i < n - 1; i++) { int a, b; scanf("%d%d", &a, &b); g[a].pb(b); g[b].pb(a); } dfs(1); decomp(1, 1); change(intv(1, n - 1, 0)); s.insert(intv(1, n - 1, 0)); for(int i = 0; i < m; i++) { int x; scanf("%d", &x); c.pb(x); } for(int i = 0; i < t; i++) { int l, r; scanf("%d%d", &l, &r); q[r].pb({l, i}); } for(int i = 1; i <= m; i++) { if(i != 1) update(c[i - 2], c[i - 1], i - 1); for(pii p : q[i]) ans[p.Y] = sum(p.X); } for(int i = 0; i < t; i++) printf("%d\n", n - ans[i]); return 0; }

Compilation message (stderr)

tourism.cpp: In function 'void decomp(int, int)':
tourism.cpp:55:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |   if(v == par[u] || v == heav[u] && u != 1) continue;
      |                     ~~~~~~~~~~~~~^~~~~~~~~
tourism.cpp: In function 'void add(int, int)':
tourism.cpp:64:6: warning: statement has no effect [-Wunused-value]
   64 |  for(x; x < OFF; x += x & -x) fen[x] += val;
      |      ^
tourism.cpp: In function 'int sum(int)':
tourism.cpp:69:6: warning: statement has no effect [-Wunused-value]
   69 |  for(x; x; x -= x & -x) ret += fen[x];
      |      ^
tourism.cpp: In function 'int main()':
tourism.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d%d%d", &n, &m, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
tourism.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
tourism.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...