제출 #619141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619141		Je_O	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5052 ms	8944 KiB

diameter

    #include<bits/stdc++.h>
    #define fi first
    #define se second
    #define mp make_pair
    #define pb push_back
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> ii;
    typedef pair<int, ii> iii;
     
    const int N = 1e5 + 5;
    const int LOG = 18;
    const int INF = 2e9 + 5;
    vector<iii> vec;
    vector<ii> lst[N];
    int dist[N];
     
    void solve_sub2(int n, int q, int w){
        int last = 0;
        while(q--){
            int d, e; cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            vec[d].fi = e;
            for(int i = 1; i <= n; ++i)lst[i].clear();
            for(int i = 0; i < n - 1; ++i){
                lst[vec[i].se.fi].pb(mp(vec[i].se.se, vec[i].fi));
                lst[vec[i].se.se].pb(mp(vec[i].se.fi, vec[i].fi));
            }
            for(int i = 1; i <= n; ++i)dist[i] = INF;
            queue<int> q;
            q.push(1);
            dist[1] = 0;
            while(!q.empty()){
                int cur = q.front(); q.pop();
                for(int i = 0; i < lst[cur].size(); ++i){
                    int nx = lst[cur][i].fi;
                    int cs = dist[cur] + lst[cur][i].se;
                    if(cs < dist[nx]){
                        dist[nx] = cs;
                        q.push(nx);
                    }
                }
            }
            ii maxdist = mp(-1, -1);
            for(int i = 1; i <= n; ++i){
                maxdist = max(maxdist, mp(dist[i], i));
            }
            for(int i = 1; i <= n; ++i)dist[i] = INF;
            q.push(maxdist.se);
            dist[maxdist.se] = 0;
            while(!q.empty()){
                int cur = q.front(); q.pop();
                for(int i = 0; i < lst[cur].size(); ++i){
                    int nx = lst[cur][i].fi;
                    int cs = dist[cur] + lst[cur][i].se;
                    if(cs < dist[nx]){
                        dist[nx] = cs;
                        q.push(nx);
                    }
                }
            }
            int ans = -1;
            for(int i = 1; i <= n; ++i){
                ans = max(ans, dist[i]);
            }
            last = ans;
            cout << ans << '\n';
        }
        return;
    }
     
    map<int, int> mep;
     
    void solve_sub3(int n, int q, int w){
        int last = 0;
        while(q--){
            int d, e; cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            --mep[vec[d].fi];
            if(mep[vec[d].fi] == 0)mep.erase(vec[d].fi);
            ++mep[e];
            vec[d].fi = e;
            auto it = mep.end();
            --it;
            int ans = it->fi;
            if(it->se > 1)ans += it->fi;
            else{
                --it;
                ans += it->fi;
            }
            last = ans;
            cout << ans << '\n';
        }
        return;
    }
     
    int par[N];
    int depth[N];
    int cost[N];
    int ar[LOG][N];
    int lf[N], rg[N];
     
    struct node{
        int mx1, mx2, lz;
    };
     
    node st[LOG][4 * N];
     
    node merge(node a, node b){
        return {max(a.mx1, b.mx1), max(min(a.mx1, b.mx1), max(a.mx2, b.mx2)), 0};
    }
     
    void build(int idx, int l, int r, int lg){
        if(l == r){
            st[lg][l] = {ar[lg][l], -1, 0};
            return;
        }
        int m = (l + r)/2;
        build(idx * 2, l, m, lg);
        build(idx * 2 + 1, m + 1, r, lg);
        st[lg][idx] = merge(st[lg][idx * 2], st[lg][idx * 2 + 1]);
        return;
    }
     
    void apply(int idx, int l, int r, int v, int lg){
        st[lg][idx].mx1 += v;
        st[lg][idx].mx2 += v;
        st[lg][idx].lz += v;
        return;
    }
     
    void pushdown(int idx, int l, int r, int lg){
        if(st[lg][idx].lz == 0)return;
        int m = (l + r)/2;
        apply(idx * 2, l, m, st[lg][idx].lz, lg);
        apply(idx * 2 + 1, m + 1, r, st[lg][idx].lz, lg);
        st[lg][idx].lz = 0;
        return;
    }
     
    void upd(int idx, int l, int r, int x, int y, int v, int lg){
        if(l > y || r < x)return;
        if(l >= x && r <= y){
            apply(idx, l, r, v, lg);
            return;
        }
        pushdown(idx, l, r, lg);
        int m = (l + r)/2;
        upd(idx * 2, l, m, x, y, v, lg);
        upd(idx * 2 + 1, m + 1, r, x, y, v, lg);
        st[lg][idx] = merge(st[lg][idx * 2], st[lg][idx * 2 + 1]);
        return;
    }
     
    node get(int idx, int l, int r, int x, int y, int lg){
        if(l > y || r < x)return {-1, -1, 0};
        if(l >= x && r <= y)return st[lg][idx];
        pushdown(idx, l, r, lg);
        int m = (l + r)/2;
        return merge(get(idx * 2, l, m, x, y, lg), get(idx * 2 + 1, m + 1, r, x, y, lg));
    }
     
    ii dfs(int idx, int p){
        par[idx] = p;
        ii res = mp(INF, 0);
        for(int i = 0; i < lst[idx].size(); ++i){
            int nx = lst[idx][i].fi;
            if(nx == p)continue;
            cost[nx] = lst[idx][i].se;
            depth[nx] = depth[idx] + 1;
            ii cur = dfs(nx, idx);
            res.fi = min(res.fi, cur.fi);
            res.se = max(res.se, cur.se);
        }
        lf[idx] = res.fi; rg[idx] = res.se;
        return res;
    }
     
    void build_ar(int l, int r){
        for(int i = l; i <= r; ++i){
            int idx = i;
            int sum_cost = 0;
            while(par[idx] != -1){
                sum_cost += cost[idx];
                idx = par[idx];
                ar[depth[idx]][i] = sum_cost;
            }
        }
        return;
    }
     
    node rs[N];
     
    int main(){
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
        int n, q, w; cin >> n >> q >> w;
        bool sub3 = true;
        for(int i = 0; i < n - 1; ++i){
            int a, b, c; cin >> a >> b >> c;
            lst[a].pb(mp(b, c));
            lst[b].pb(mp(a, c));
            vec.pb(mp(c, mp(a, b)));
            ++mep[c];
            if(a != 1 && b != 1)sub3 = false;
        }
        if(n <= 5000 && q <= 5000){
            solve_sub2(n, q, w);
            return 0;
        }
        if(sub3){
            solve_sub3(n, q, w);
            return 0;
        }
        mep.clear();
        dfs(1, -1);
        int id_l = 0;
        for(int i = 1; i <= n; ++i){
            if(lst[i].size() == 1){
                id_l = i;
                break;
            }
        }
        build_ar(id_l, n);
        for(int i = 0; i < LOG; ++i)build(1, 1, n, i);
        for(int i = 1; i < id_l; ++i){
            rs[i] = get(1, 1, n, lf[i], rg[i], depth[i]);
            mep[rs[i].mx1 + rs[i].mx2]++;
        }
        int last = 0;
        while(q--){
            int d, e; cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            int x = vec[d].se.fi, y = vec[d].se.se;
            if(depth[x] < depth[y])swap(x, y);
            int idx = x;
            while(par[idx] != -1){
                idx = par[idx];
                int last_sum = rs[idx].mx1 + rs[idx].mx2;
                mep[last_sum]--;
                upd(1, 1, n, lf[x], rg[x], e - cost[x], depth[idx]);
                rs[idx] = get(1, 1, n, lf[idx], rg[idx], depth[idx]);
                mep[rs[idx].mx1 + rs[idx].mx2]++;
            }
            cost[x] = e;
            vec[d].fi = e;
            auto it = mep.end();
            --it;
            while(it->se == 0){
                mep.erase(it->fi);
                --it;
            }
            int ans = it->fi;
            if(it->se > 1){
                ans += it->fi;
            }else{
                while(it->se == 0){
                    mep.erase(it->fi);
                    --it;
                }
                --it;
                ans += it->fi;
            }
            last = ans;
            cout << ans << '\n';
        }
        return 0;
    }

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

diameter.cpp: In function 'void solve_sub2(int, int, int)':
diameter.cpp:36:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                 for(int i = 0; i < lst[cur].size(); ++i){
      |                                ~~^~~~~~~~~~~~~~~~~
diameter.cpp:54:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for(int i = 0; i < lst[cur].size(); ++i){
      |                                ~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'ii dfs(int, int)':
diameter.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for(int i = 0; i < lst[idx].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27