oj.uz

답안 #237854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237854 2020-06-09T06:02:33 Z Mercenary Cats or Dogs (JOI18_catdog) C++14
0 / 100
 16 ms 11904 KB 
#include<bits/stdc++.h>
//#include "catdog.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int sz[maxn];
int a[maxn];
int n , q;
vector<int> adj[maxn];
int chainhead[maxn];
int chainid[maxn];
int specid[maxn];

int chainsz[maxn];

int par[maxn];


struct seg{
    struct node{
        int dp[2][2];
        int getans(){
            int res = 1e5;
            for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j)res = min(res , dp[i][j]);
            return res;
        }
        friend node operator + (const node & a , const node & b){
            node res;
            for(int i = 0 ; i < 2 ; ++i)for(int j = 0 ; j < 2 ; ++j){
                res.dp[i][j] = 1e5;
                for(int k = 0 ; k < 2 ; ++k)for(int t = 0 ; t < 2 ; ++t){
                    res.dp[i][j] = min(res.dp[i][j] , a.dp[i][k] + b.dp[t][j] + (k ^ t));
                }
            }
            return res;
        }
    };
    vector<node> s;
    int n;
    void build(int x , int l , int r){
        if(l == r){
            s[x].dp[0][1] = s[x].dp[1][0] = 1e5;
            return;
        }
        int mid = l + r >> 1;
        build(x * 2 , l , mid);build(x * 2 + 1 , mid + 1 , r);
        s[x] = s[x * 2] + s[x * 2 + 1];
    }
    void init(){
        s.resize((n + 3) * 4);
        build(1,1,n);
    }
    void update(int x , int &pos , int &delta0 , int &delta1 , int l , int r){
        if(l == r){
            s[x].dp[0][0] += delta0;
            s[x].dp[1][1] += delta1;
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)update(x * 2 , pos , delta0 , delta1 , l , mid);
        else update(x * 2 + 1, pos , delta0 , delta1 , mid + 1 , r);
        s[x] = s[x * 2] + s[x * 2 + 1];
    }
}s[maxn];

void update(int u , int delta0 , int delta1){
    while(u > 0){
        int curchain = chainid[u];
        auto pre = s[curchain].s[1];
        s[curchain].update(1,specid[u],delta0,delta1,1,s[curchain].n);
        auto now = s[curchain].s[1];
        delta0 = min({now.dp[0][0],now.dp[0][1],now.dp[1][0]+1,now.dp[1][1]+1})
            - min({pre.dp[0][0],pre.dp[0][1],pre.dp[1][0]+1,pre.dp[1][1]+1});
        delta1 = min({now.dp[0][0] + 1 ,now.dp[0][1] + 1 ,now.dp[1][0],now.dp[1][1]})
            - min({pre.dp[0][0] + 1 ,pre.dp[0][1] + 1 ,pre.dp[1][0],pre.dp[1][1]});
        u = par[chainhead[curchain]];
    }
}
void dfs(int u , int par){
    sz[u] = 1;
    for(auto c : adj[u]){
        if(c == par)continue;
        ::par[c] = u;
        dfs(c , u);
        sz[u] += sz[c];
    }
}

int nTime = 0;

void hld(int u , int par){
    ii best = mp(0,0);
    chainid[u] = nTime;
    specid[u] = ++s[nTime].n;
    if(chainhead[nTime] == 0)chainhead[nTime] = u;
    for(auto c : adj[u]){
        if(c == par)continue;
        best = max(best,mp(sz[c],c));
    }
    if(best.second != 0)hld(best.second,u);
    for(auto c : adj[u]){
        if(c == par || c == best.second)continue;
        ++nTime;
        hld(c , u);
    }
}

void initialize(int N, vector<int> a, vector<int> b) {
    n = N;
    for(int i = 0 ; i < n - 1 ; ++i){
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
    for(int i = 1 ; i <= n ; ++i)a[i] = 3;
    dfs(1,0);
    hld(1,0);
    for(int i = 0 ; i <= nTime ; ++i){
        s[i].init();
    }
}

int cat(int v) {
    a[v] = 1;
    update(v,1e5,0);
    return s[0].s[1].getans();
}

int dog(int v) {
    a[v] = 2;
    update(v,0,1e5);
    return s[0].s[1].getans();
}

int neighbor(int v) {
    if(a[v] == 1)update(v,-1e5,0);
    else update(v,0,-1e5);
    return s[0].s[1].getans();
}

Compilation message

catdog.cpp: In member function 'void seg::build(int, int, int)':
catdog.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
catdog.cpp: In member function 'void seg::update(int, int&, int&, int&, int, int)':
catdog.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Runtime error 16 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Runtime error 16 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 9 ms 5888 KB Output is correct
3 Runtime error 16 ms 11904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -