提交记录 10245


用户 题目 状态 得分 用时 内存 语言 代码长度
rainy noip18f. 【NOIP2018】保卫王国 Accepted 100 1.23 s 22 MB + 80 KB C++11 3.10 KB
提交时间 评测时间
2019-09-07 19:15:15 2019-09-07 19:15:44
// luogu-judger-enable-o2
#include<bits/stdc++.h>

using namespace std;

typedef long long int_t;

const int_t maxn = 100010;
const int_t inf = 2147483647ll * 192608;
#define lson son[rt][0]
#define rson son[rt][1]

struct matrix{
    int_t mat[3][3];
    matrix(){mat[1][1] = mat[1][2] = mat[2][1] = mat[2][2] = -inf;}
    int_t MAX(){return max(mat[1][1],mat[2][1]);}
    matrix operator *(matrix b){
        matrix c;
        for(int_t i=1;i<=2;i++)
            for(int_t j=1;j<=2;j++)
                for(int_t k=1;k<=2;k++)
                    c.mat[i][j] = max(c.mat[i][j],mat[i][k] + b.mat[k][j]);
        return c;
    }
};

matrix mat[maxn];
int_t f[maxn][2],fa[maxn],val[maxn],son[maxn][2];
vector<int_t> G[maxn];

void pushup(int_t rt){
    mat[rt] = matrix();
    mat[rt].mat[1][1] = mat[rt].mat[1][2] = f[rt][0];
    mat[rt].mat[2][1] = f[rt][1];
    if(lson) mat[rt] = mat[lson] * mat[rt];
    if(rson) mat[rt] = mat[rt] * mat[rson];
}

bool isroot(int_t rt) { return son[fa[rt]][0] != rt && son[fa[rt]][1] != rt; }

void rotate(int_t rt){
    int_t fat = fa[rt], gfa = fa[fat], rs = son[fat][1] == rt, mus = son[rt][!rs];
    if(!isroot(fat)) son[gfa][son[gfa][1] == fat] = rt; son[rt][!rs] = fat; son[fat][rs] = mus;
    if(mus) fa[mus] = fat; fa[rt] = gfa; fa[fat] = rt;
    pushup(fat); pushup(rt);
}

void splay(int_t rt){
    while(!isroot(rt)){
        int_t fat = fa[rt],gfa = fa[fat];
        if(!isroot(fat)) rotate(((son[fat][1] == rt) ^ (son[gfa][1] == fat)) ? rt : fat);
        rotate(rt);
    }
}

void access(int_t rt){
    for(int_t y = 0;rt;y = rt,rt = fa[rt]){
        splay(rt);
        if(rson) 
            f[rt][0] += mat[rson].MAX(),
            f[rt][1] += mat[rson].mat[1][1];
        if(y)
            f[rt][0] -= mat[y].MAX(),
            f[rt][1] -= mat[y].mat[1][1];
        rson = y;
        pushup(rt);
    }
}

void init(int_t rt){
    f[rt][1] = val[rt];
    for(int_t to : G[rt]){
        if(to == fa[rt]) continue;
        fa[to] = rt;
        init(to);
        f[rt][0] += max(f[to][0],f[to][1]);
        f[rt][1] += f[to][0];
    }
    mat[rt].mat[1][1] = mat[rt].mat[1][2] = f[rt][0];
    mat[rt].mat[2][1] = f[rt][1]; 
}

int_t read(){
    int_t x = 0,w = 1;char ch = 0;
    while(!isdigit(ch)) {ch = getchar();if(ch == '-') w = -1;}
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * w;
}

void modify(int_t x,int_t y){
    access(x); splay(x);
    f[x][1] += y; val[x] += y;
    pushup(x); 
}

int main(){
    int_t n = read(),m = read(),res = 0; string str;cin>>str;
    for(int_t i=1;i<=n;i++) val[i] = read(),res += val[i];
    for(int_t i=1;i<n;i++){
        int_t u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init(1);
    while(m--){
        int_t a = read(),x = read(),b = read(),y = read();
        modify( a,x ? -inf : inf );
        modify( b,y ? -inf : inf );
        splay(1);
        if(!x) res += inf; if(!y) res += inf;
        int_t ans = res - mat[1].MAX();
        printf("%lld\n",ans > inf ? -1 : ans);
        if(!x) res -= inf; if(!y) res -= inf;
        modify( a,x ? inf : -inf );
        modify( b,y ? inf : -inf );
    }
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.584 ms8 MB + 80 KBAcceptedScore: 4

Testcase #21.571 ms8 MB + 80 KBAcceptedScore: 4

Testcase #31.558 ms8 MB + 80 KBAcceptedScore: 4

Testcase #41.576 ms8 MB + 80 KBAcceptedScore: 4

Testcase #52.024 ms8 MB + 88 KBAcceptedScore: 4

Testcase #62.027 ms8 MB + 88 KBAcceptedScore: 4

Testcase #72.012 ms8 MB + 84 KBAcceptedScore: 4

Testcase #815.71 ms8 MB + 356 KBAcceptedScore: 4

Testcase #915.604 ms8 MB + 356 KBAcceptedScore: 4

Testcase #1014.864 ms8 MB + 296 KBAcceptedScore: 4

Testcase #1114.897 ms8 MB + 296 KBAcceptedScore: 4

Testcase #12664.948 ms22 MB + 80 KBAcceptedScore: 4

Testcase #13663.437 ms22 MB + 80 KBAcceptedScore: 4

Testcase #14988.112 ms21 MB + 908 KBAcceptedScore: 4

Testcase #15988.192 ms21 MB + 912 KBAcceptedScore: 4

Testcase #16988.345 ms21 MB + 912 KBAcceptedScore: 4

Testcase #171.23 s22 MB + 80 KBAcceptedScore: 4

Testcase #18241.773 ms16 MB + 404 KBAcceptedScore: 4

Testcase #19241.631 ms16 MB + 404 KBAcceptedScore: 4

Testcase #20590.487 ms19 MB + 88 KBAcceptedScore: 4

Testcase #21590.014 ms19 MB + 80 KBAcceptedScore: 4

Testcase #22756.188 ms18 MB + 912 KBAcceptedScore: 4

Testcase #231.12 s19 MB + 80 KBAcceptedScore: 4

Testcase #241.121 s19 MB + 84 KBAcceptedScore: 4

Testcase #251.12 s19 MB + 96 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2019-09-20 12:25:47 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用