제출 #414931

#제출 시각아이디문제언어결과실행 시간메모리
414931Pro_ktmrConstruction of Highway (JOI18_construction)C++17
100 / 100
1327 ms87432 KiB
#pragma GCC target ("avx2") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("O3") #include "bits/stdc++.h" #include <unordered_set> #include <unordered_map> #include <random> using namespace std; typedef long long ll; typedef unsigned long long ull; constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/ #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rep(i, n) for(int (i)=0; (i)<(n); (i)++) template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; } constexpr int dy[4]={-1,0,1,0}; constexpr int dx[4]={0,-1,0,1}; template<typename T> struct SegmentTree{ private: int n, N; vector<T> node; function<T(T, T)> F; T E; public: void init(int _n, function<T(T, T)> f, T e){ F = f; E = e; n = _n; N = 1; while(N < n) N = (N<<1); node.assign(2*N-1, e); } void init(vector<T> v, function<T(T, T)> f, T e){ F = f; E = e; n = v.size(); N = 1; while(N < n) N = (N<<1); node.assign(2*N-1, e); for(int i=0; i<n; i++) node[N-1+i] = v[i]; for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]); } T& operator [](int a){ return node[N-1+a]; } void update(int a, T x){ a += N-1; node[a] = x; while(a > 0){ a = (a-1)>>1; node[a] = F(node[(a<<1)+1], node[(a<<1)+2]); } } T query(int a, int b, int k=0, int l=0, int r=-1){ if(r == -1) r = N; if(b <= l || r <= a) return E; if(a <= l && r <= b) return node[k]; return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r)); } int find_right(function<bool(T)> g, int a){ if(!g(E)) return -1; T t = E; return min(find_right(g, a, 0, 0, N, t), n); } int find_right(function<bool(T)> g, int a, int k, int l, int r, T &t){ if(r-l == 1){ t = F(t, node[k]); return g(t) ? r : a; } int m = (l + r) >> 1; if(m <= a) return find_right(g, a, (k<<1)+2, m, r, t); if(a <= l && g(F(t, node[k]))){ t = F(t, node[k]); return r; } int L = find_right(g, a, (k<<1)+1, l, m, t); if(L < m) return L; int R = find_right(g, a, (k<<1)+2, m, r, t); return max(L, R); } int find_left(function<bool(T)> g, int b){ if(!g(E)) return n + 1; T t = E; return find_left(g, b, 0, 0, N, t); } int find_left(function<bool(T)> g, int b, int k, int l, int r, T t){ if(r-l == 1){ t = F(node[k], t); return g(t) ? l : b; } int m = (l + r) >> 1; if(b <= m) return find_left(g, b, (k<<1)+1, l, m, t); if(r <= b && g(F(node[k], t))){ t = F(node[k], t); return l; } int R = find_left(g, b, (k<<1)+2, m, r, t); if(m < R) return R; int L = find_left(g, b, (k<<1)+1, l, m, t); return min(L, R); } }; int N; int C[100000]; int A[100000], B[100000]; vector<int> z; int par[100000] ={-1}; vector<int> chi[100000]; int s[100000] ={}; int siz(int v){ if(s[v] != 0) return s[v]; s[v] = 1; for(int i=0; i<chi[v].size(); i++) s[v] += siz(chi[v][i]); return s[v]; } int d[100000] ={}; int depth(int v){ if(d[v] != 0) return d[v]; if(par[v] == -1) return 0; return d[v] = 1 + depth(par[v]); } vector<int> hld; int pre[100000]; int top[100000]; void HLD(int v, int a){ pre[v] = hld.size(); hld.pb(v); top[v] = a; if(chi[v].size() == 0) return; int M = 0; int idx = -1; for(int i=0; i<chi[v].size(); i++){ if(chmax(M, siz(chi[v][i]))) idx = i; } HLD(chi[v][idx], a); for(int i=0; i<chi[v].size(); i++){ if(i != idx) HLD(chi[v][i], chi[v][i]); } } vector<pair<int, int>> query(int v){ // [,] vector<pair<int, int>> ret; while(v != -1){ ret.pb({pre[top[v]], pre[v]}); v = par[top[v]]; } reverse(all(ret)); return ret; } struct range{ int l, r, a; }; stack<range> st[100000]; SegmentTree<ll> segtree; signed main(){ scanf("%d", &N); rep(i, N){ scanf("%d", C+i); z.pb(C[i]); } sort(all(z)); rep(i, N) C[i] = lower_bound(all(z), C[i]) - z.begin(); rep(i, N-1){ scanf("%d%d", A+i, B+i); A[i]--; B[i]--; par[B[i]] = A[i]; chi[A[i]].pb(B[i]); } HLD(0, 0); st[0].push({0,0,C[0]}); segtree.init(N, [](ll a, ll b){ return a+b; }, 0); rep(i, N-1){ ll ans = 0; auto v = query(B[i]); vector<int> memo; rep(j, v.size()){ while(st[v[j].first].size() > 0 && st[v[j].first].top().l <= v[j].second){ // O(N log N) range r = st[v[j].first].top(); st[v[j].first].pop(); if(v[j].second < r.r){ st[v[j].first].push({v[j].second+1, r.r, r.a}); r.r = v[j].second; } ans += segtree.query(r.a+1, N) * (ll)(r.r - r.l + 1); segtree.update(r.a, segtree[r.a] + r.r - r.l + 1); memo.pb(r.a); } st[v[j].first].push({v[j].first, v[j].second, C[B[i]]}); } printf("%lld\n", ans); rep(j, memo.size()) segtree.update(memo[j], 0); } }

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

construction.cpp: In function 'int siz(int)':
construction.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0; i<chi[v].size(); i++) s[v] += siz(chi[v][i]);
      |                  ~^~~~~~~~~~~~~~
construction.cpp: In function 'void HLD(int, int)':
construction.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0; i<chi[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~
construction.cpp:146:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int i=0; i<chi[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:171:5: note: in expansion of macro 'rep'
  171 |     rep(i, N){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:176:5: note: in expansion of macro 'rep'
  176 |     rep(i, N) C[i] = lower_bound(all(z), C[i]) - z.begin();
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:177:5: note: in expansion of macro 'rep'
  177 |     rep(i, N-1){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:188:5: note: in expansion of macro 'rep'
  188 |     rep(i, N-1){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:192:9: note: in expansion of macro 'rep'
  192 |         rep(j, v.size()){
      |         ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
construction.cpp:192:9: note: in expansion of macro 'rep'
  192 |         rep(j, v.size()){
      |         ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:207:9: note: in expansion of macro 'rep'
  207 |         rep(j, memo.size()) segtree.update(memo[j], 0);
      |         ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
construction.cpp:207:9: note: in expansion of macro 'rep'
  207 |         rep(j, memo.size()) segtree.update(memo[j], 0);
      |         ^~~
construction.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
construction.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d", C+i);
      |         ~~~~~^~~~~~~~~~~
construction.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         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...