結果

問題 No.1197 モンスターショー
ユーザー chocorusk
提出日時 2020-08-22 18:12:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 523 ms / 3,000 ms
コード長 3,965 bytes
コンパイル時間 1,827 ms
コンパイル使用メモリ 131,004 KB
最終ジャッジ日時 2025-01-13 11:32:19
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:150:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |         scanf("%d %d %d", &n, &k, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:155:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  155 |         scanf("%d", &c[i]);
      |         ~~~~~^~~~~~~~~~~~~
main.cpp:161:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  161 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:170:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  170 |         int t; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
main.cpp:173:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  173 |             scanf("%d %d", &p, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:181:25: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  181 |             int e; scanf("%d", &e);
      |                    ~~~~~^~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
struct LinkCutTree{
    struct Node{
        Node *l, *r, *p;
        bool rev;
        int idx, val, sz, szl;
        ll cost, sum, suml, costs, sum2;
        Node(int val, int idx, ll cost):cost(cost), costs(cost), sum(0), sum2(0), suml(0), idx(idx), val(val), sz(val), szl(0), rev(false), l(nullptr
            ), r(nullptr), p(nullptr){}
        bool is_root(){
            return !p || (p->l!=this && p->r!=this);
        }
    };
    vector<Node*> v;
    LinkCutTree(int n){
        v.resize(n);
        for(int i=0; i<n; i++) v[i]=new Node(0, i, 0);
    }
    void toggle(Node *t){
        if(!t) return;
        swap(t->sum, t->sum2);
        swap(t->l, t->r);
        t->rev^=true;
    }
    void push(Node *t){
        if(!t) return;
        if(t->rev){
            toggle(t->l);
            toggle(t->r);
            t->rev=false;
        }
    }
    void update(Node *t){
        t->sz=t->val+t->szl, t->costs=t->cost;
        if(t->l) t->sz+=t->l->sz, t->costs+=t->l->costs;
        if(t->r) t->sz+=t->r->sz, t->costs+=t->r->costs;
        t->sum=t->suml+t->cost*t->szl;
        t->sum2=t->suml+t->cost*t->szl;
        if(t->l) t->sum+=t->l->sum, t->sum2+=t->l->sum2, t->sum+=t->l->costs*(t->val+t->szl), t->sum2+=t->l->sz*t->cost;
        if(t->r) t->sum+=t->r->sum, t->sum2+=t->r->sum2, t->sum+=t->r->sz*t->cost, t->sum2+=t->r->costs*(t->val+t->szl);
        if(t->l && t->r) t->sum+=t->l->costs*t->r->sz, t->sum2+=t->r->costs*t->l->sz;
    }
    void rotate(Node *t){
        Node *p=t->p, *pp=p->p, *ch;
        if(p->l==t) ch=t->r;
        else ch=t->l;
        if(pp){
            if(pp->l==p) pp->l=t;
            else if(pp->r==p) pp->r=t;
        }
        t->p=pp;
        if(p->l==t) t->r=p;
        else t->l=p;
        p->p=t;
        if(p->l==t) p->l=ch;
        else p->r=ch;
        if(ch) ch->p=p;
        update(p);
        update(t);
    }
    int state(Node *t){
        if(t->is_root()) return 0;
        else if(t->p->l==t) return 1;
        else return -1;
    }
    void splay(Node *t){
        push(t);
        while(state(t)){
            if(!state(t->p)){
                push(t->p); push(t);
                rotate(t);
            }else{
                push(t->p->p); push(t->p); push(t);
                if(state(t->p)==state(t)){
                    rotate(t->p);
                    rotate(t);
                }else{
                    rotate(t);
                    rotate(t);
                }
            }
        }
    }
    Node *expose(Node *t){
        Node *rp=nullptr;
        for(Node *now=t; now; now=now->p){
            splay(now);
            if(rp){
                now->szl-=rp->sz;
                now->suml-=rp->sum;
            }
            if(now->r){
                now->szl+=now->r->sz;
                now->suml+=now->r->sum;
            }
            now->r=rp;
            update(now);
            rp=now;
        }
        splay(t);
        return rp;
    }
    void link(Node *c, Node *p){
        expose(c);
        expose(p);
        p->r=c;
        c->p=p;
        update(p);
    }
    void cut(Node *c){
        expose(c);
        c->l->p=nullptr;
        c->l=nullptr;
        update(c);
    }
    void evert(Node *t){
        expose(t);
        toggle(t);
        push(t);
    }
};
int main()
{
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    LinkCutTree lct(n);
    using node=LinkCutTree::Node;
    int c[100010];
    for(int i=0; i<k; i++){
        scanf("%d", &c[i]);
        c[i]--;
        lct.v[c[i]]->val++;
    }
    for(int i=0; i<n-1; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        node *e=new node(0, i+n, 1);
        lct.v.push_back(e);
        lct.link(e, lct.v[a]);
        lct.evert(e);
        lct.link(e, lct.v[b]);
    }
    while(q--){
        int t; scanf("%d", &t);
        if(t==1){
            int p, d;
            scanf("%d %d", &p, &d);
            p--; d--;
            lct.expose(lct.v[c[p]]);
            lct.v[c[p]]->val--;
            c[p]=d;
            lct.expose(lct.v[c[p]]);
            lct.v[c[p]]->val++;
        }else{
            int e; scanf("%d", &e);
            e--;
            lct.evert(lct.v[e]);
            printf("%lld\n", lct.v[e]->sum);
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0