#724418 (C++17) No.1787 Do Use Dynamic Tree

提出ソース

結果

問題	No.1787 Do Use Dynamic Tree
ユーザー	👑 Nachia
提出日時	2021-12-16 18:55:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,442 bytes
コンパイル時間	2,106 ms
コンパイル使用メモリ	137,368 KB
実行使用メモリ	57,044 KB
最終ジャッジ日時	2024-09-13 16:38:24
合計ジャッジ時間	32,161 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	806 ms 57,044 KB
testcase_29	AC	782 ms 57,024 KB
testcase_30	AC	832 ms 56,944 KB
testcase_31	AC	1,395 ms 51,660 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	AC	999 ms 51,612 KB
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code


#include <atcoder/segtree>




#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct heavy_light_decomposition{
private:

  int N;
  vector<int> P;
  vector<int> PP;
  vector<int> PD;
  vector<int> D;
  vector<int> I;

  vector<int> rangeL;
  vector<int> rangeR;

public:

  heavy_light_decomposition(const vector<vector<int>>& E = {{}}){
    N = E.size();
    P.assign(N, -1);
    I = {0};
    I.reserve(N);
    for(int i=0; i<I.size(); i++){
      int p = I[i];
      for(int e : E[p]) if(P[p] != e){
        I.push_back(e);
        P[e] = p;
      }
    }
    vector<int> Z(N, 1);
    vector<int> nx(N, -1);
    PP.resize(N);
    for(int i=0; i<N; i++) PP[i] = i;
    for(int i=N-1; i>=1; i--){
      int p = I[i];
      Z[P[p]] += Z[p];
      if(nx[P[p]] == -1) nx[P[p]] = p;
      if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
    }

    for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;

    PD.assign(N,N);
    PD[0] = 0;
    D.assign(N,0);
    for(int p : I) if(p != 0){
      PP[p] = PP[PP[p]];
      PD[p] = min(PD[PP[p]], PD[P[p]]+1);
      D[p] = D[P[p]]+1;
    }
    
    rangeL.assign(N,0);
    rangeR.assign(N,0);
    vector<int> dfs;
    dfs.push_back(0);
    while(dfs.size()){
      int p = dfs.back();
      rangeR[p] = rangeL[p] + Z[p];
      int ir = rangeR[p];
      dfs.pop_back();
      for(int e : E[p]) if(P[p] != e) if(e != nx[p]){
        rangeL[e] = (ir -= Z[e]);
        dfs.push_back(e);
      }
      if(nx[p] != -1){
        rangeL[nx[p]] = rangeL[p] + 1;
        dfs.push_back(nx[p]);
      }
    }

    I.resize(N);
    for(int i=0; i<N; i++) I[rangeL[i]] = i;
  }

  int depth(int p) const {
    return D[p];
  }

  int lca(int u, int v) const {
    if(PD[u] < PD[v]) swap(u, v);
    while(PD[u] > PD[v]) u = P[PP[u]];
    while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
    return (D[u] > D[v]) ? v : u;
  }

  int dist(int u, int v) const {
    return depth(u) + depth(v) - depth(lca(u,v)) * 2;
  }

  vector<pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const {
    vector<pair<int,int>> res;
    while(PD[r] < PD[c]){
      res.push_back({ rangeL[PP[c]], rangeL[c]+1 });
      c = P[PP[c]];
    }
    if(PP[r] != PP[c]) return {};
    if(D[r] > D[c]) return {};
    res.push_back({ rangeL[r], rangeL[c]+1 });
    if(!include_root){
      res.back().first++;
      if(res.back().first == res.back().second) res.pop_back();
    }
    if(!reverse_path) reverse(res.begin(),res.end());
    return res;
  }

  const vector<int>& idxs() const {
    return rangeL;
  }
  const vector<int>& invidxs() const {
    return I;
  }

  int meet(int x, int y, int z) const {
    return lca(x,y) ^ lca(y,z) ^ lca(x,z);
  }

  int jump(int from, int to, int d) const {
    int g = lca(from,to);
    int dist0 = D[from] - D[g] * 2 + D[to];
    if(dist0 > d) return -1;
    int p = from;
    if(D[from] - D[g] > d){ p = to; d = dist0 - d; }
    while(D[p] - D[PP[p]] > d){
      d -= D[p] - D[PP[p]] + 1;
      p = P[PP[p]];
    }
    return I[rangeL[p] - d];
  }
  
  int heavy_path_child(int p){
    int ip = rangeL[p];
    if(ip == N-1) return -1;
    int cand = I[ip + 1];
    if(PP[cand] != PP[p]) return -1;
    return cand;
  }
  
  int parent(int p){ return P[p]; }
  
};




#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

namespace ruq {
    map<int,int> rq;
    void init(){
        rq[-1] = 0;
    }
    int query(int p){
        auto i = rq.upper_bound(p);
        i--;
        return i->second;
    }
    void apply(int l, int r, int updval){
        if(l >= r) return;
        int lastval = query(l);
        auto i = rq.lower_bound(l);
        while(true){
            if(i == rq.end()) break;
            if(r < i->first) break;
            lastval = i->second;
            i = rq.erase(i);
        }
        rq.insert(make_pair(l, updval));
        rq.insert(make_pair(r, lastval));
    }
}


int N;
vector<int> A;
vector<vector<int>> E;
heavy_light_decomposition hld;
vector<set<pair<int,int>, greater<pair<int,int>>>> children;
vector<int> maxchild;
vector<int> ismaxchild;

namespace all_is_good_query{
    using S = int;
    S op(S l, S r){ return l & r; }
    S e(){ return 1; }
    using rq = atcoder::segtree<S,op,e>;
    bool check(S x){ return x; }
}


all_is_good_query::rq isparentmax_rq;
all_is_good_query::rq isparentparentmax_rq;
all_is_good_query::rq ismaxchild_rq;

int is_parent_max(int p){
    if(p == 0) return 0;
    if(maxchild[p] < 0) return 1;
    return (A[hld.parent(p)] > A[maxchild[p]]) ? 1 : 0;
}

int is_parent_parent_max(int p){
    if(hld.depth(p) < 2) return 0;
    int pp = hld.parent(p);
    int ppp = hld.parent(pp);
    if(children[pp].size() <= 1) return 1;
    if(maxchild[pp] != p) return (A[ppp] > A[maxchild[pp]]) ? 1 : 0;
    auto i = children[pp].begin(); i++;
    return (A[ppp] > A[i->first]) ? 1 : 0;
}

int solve_parentmax(int x){
    if(x == 0) return x;
    if(is_parent_max(x) == 0) return x;
    auto path = hld.path(0,x);
    /*
    while(!path.empty()){
        auto p = path.back();
        path.pop_back();
        int l = isparentmax_rq.min_left(p.second, all_is_good_query::check);
        if(p.first + 1 < l){ return hld.invidxs()[l]; }
        int pathp = hld.invidxs()[p.first];
        if(!is_parent_max(pathp)) return pathp;
    }
    */
    while(!path.empty()){
        auto p = path.back();
        path.pop_back();
        int l = isparentparentmax_rq.min_left(p.second, all_is_good_query::check);
        l = min(max(l, p.first + 2), p.second);
        if(p.first + 2 < l){ return hld.invidxs()[l-2]; }
        //cout << "       p.first = " << p.first << endl;
        //cout << "       p.second = " << p.second << endl;
        while(l != p.first){
            l--;
            int pathp = hld.invidxs()[l];
            //cout << "       pathp = " << pathp << endl;
            if(is_parent_parent_max(pathp)) continue;
            return hld.parent(hld.invidxs()[l]);
        }
    }
    return 0;
}

int solve_maxchild(int x){
    auto path = hld.path(0,x);
    while(!path.empty()){
        auto p = path.back();
        path.pop_back();
        int l = ismaxchild_rq.min_left(p.second, all_is_good_query::check);
        if(p.first + 1 < l){ return hld.invidxs()[l]; }
        int pathp = hld.idxs()[p.first];
        if(!ismaxchild[pathp]) return pathp;
    }
    return 0;
}


void set_A(int p, int a){
    int heavy_child = hld.heavy_path_child(p);
    int parent = hld.parent(p);
    int heavy_child2 = -1;
    if(heavy_child != -1) heavy_child2 = hld.heavy_path_child(heavy_child);
    
    if(parent != -1){
        children[parent].erase(make_pair(A[p], p));
    }
    
    A[p] = a;
    
    if(parent != -1){
        children[parent].insert(make_pair(A[p], p));
        ismaxchild[maxchild[parent]] = 0;
        maxchild[parent] = children[parent].begin() -> second;
        ismaxchild[maxchild[parent]] = 1;
        ismaxchild_rq.set(hld.idxs()[p], ismaxchild[p]);

        int updv = ruq::query(hld.idxs()[maxchild[parent]]);
        int updr = solve_maxchild(parent);
        //cout << "     updr = " << updr << endl;
        for(auto path : hld.path(updr, parent)) ruq::apply(path.first, path.second, updv);
    }

    //if(heavy_child != -1) isparentmax_rq.set(hld.idxs()[heavy_child], is_parent_max(heavy_child));
    //if(parent != -1) isparentmax_rq.set(hld.idxs()[parent], is_parent_max(parent));
    if(heavy_child2 != -1) isparentparentmax_rq.set(hld.idxs()[heavy_child2], is_parent_parent_max(heavy_child2));
    isparentparentmax_rq.set(hld.idxs()[p], is_parent_parent_max(p));
    
    //cout << "A updated " << endl;
    //cout << "    A = ["; for(auto a : A) cout << " " << a; cout << " ]" << endl;
    //cout << "    maxchild = ["; for(auto a : maxchild) cout << " " << a; cout << " ]" << endl;
    //cout << "    ismaxchild = ["; for(auto a : ismaxchild) cout << " " << a; cout << " ]" << endl;
    //cout << "    isparentmax = ["; rep(i,N) cout << " " << is_parent_max(i); cout << " ]" << endl;
    //cout << "    isparentparentmax = ["; rep(i,N) cout << " " << isparentparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl;
    //cout << "    query = ["; rep(i,N) cout << " " << ruq::query(hld.idxs()[i]); cout << " ]" << endl;
}


int query(int u, int v){
    int au = A[u];
    int av = A[v];
    set_A(u, av);
    set_A(v, au);
    //cout << "u = " << u << ", v = " << v << endl;
    int g = solve_parentmax(u);
    //cout << "g = " << g << endl;
    int ans = g;
    if(u != g){
        if(children[g].size() <= 1) g = -1;
        else if(hld.lca(u, maxchild[g]) == maxchild[g]){
            auto i = children[g].begin();
            i++;
            g = i -> second;
        }
    }
    if(g != -1) ans = ruq::query(hld.idxs()[g]);
    //cout << "ans = " << ans << endl;
    return ans;
}


int main(void){
    cin >> N;
    A.resize(N);
    rep(i,N) A[i] = i;
    E.resize(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    
    //cout << "##" << endl;
    
    hld = heavy_light_decomposition(E);
    E.clear();
    E.resize(N);
    children.resize(N);
    
    for(int i=1; i<N; i++){
        E[hld.parent(i)].push_back(i);
        children[hld.parent(i)].insert(make_pair(A[i],i));
    }
    
    //cout << "##" << endl;
    
    maxchild.assign(N,-1);
    rep(i,N) if(!children[i].empty()) maxchild[i] = children[i].begin() -> second;
    ismaxchild.assign(N,0);
    for(int i=1; i<N; i++) ismaxchild[i] = (maxchild[hld.parent(i)] == i) ? 1 : 0;
    
    //cout << "##" << endl;
    
    isparentmax_rq = all_is_good_query::rq(N);
    rep(i,N) isparentmax_rq.set(hld.idxs()[i], is_parent_max(i));
    isparentparentmax_rq = all_is_good_query::rq(N);
    rep(i,N) isparentparentmax_rq.set(hld.idxs()[i], is_parent_parent_max(i));
    ismaxchild_rq = all_is_good_query::rq(ismaxchild);
    
    //cout << "##" << endl;
    
    //set_A(1,4);
    //set_A(0,5);
    
    int prevans = 0;
    int Q; cin >> Q;

    ruq::init();

    {
        vector<int> dp(N);
        rep(i,N) dp[i] = i;
        for(int i=N-1; i>=0; i--){
            int p = hld.invidxs()[i];
            if(children[p].empty()) continue;
            dp[p] = dp[maxchild[p]];
        }
        rep(p,N) ruq::rq[hld.idxs()[p]] = dp[p];
    }
    
    //cout << "initialized " << endl;
    //cout << "    ismaxchild = ["; for(auto a : ismaxchild) cout << " " << a; cout << " ]" << endl;
    //cout << "    isparentmax = ["; rep(i,N) cout << " " << isparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl;
    //cout << "    isparentparentmax = ["; rep(i,N) cout << " " << isparentparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl;
    //cout << "    heavy child = ["; rep(i,N) cout << " " << hld.heavy_path_child(i) << flush; cout << " ]" << endl;
    //cout << "    parent = ["; rep(i,N) cout << " " << hld.parent(i) << flush; cout << " ]" << endl;

    rep(queryid, Q){
        int u,v; cin >> u >> v;
        u = (u+N-1+prevans) % N + 1;
        v = (v+N-1+prevans) % N + 1;
        u--; v--;
        int ans = query(u,v) + 1;
        cout << ans << "\n";
        prevans = ans;
    }
    
    return 0;
} 
 
struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

yukicoder

結果

テストケース

ソースコード