oj.uz

답안 #124303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124303 2019-07-03T01:18:03 Z duality Unique Cities (JOI19_ho_t5) C++11
64 / 100
 1649 ms 99196 KB 
#define DEBUG 1

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

int N,logn;
vi adjList[200000];
int C[200000];
int parent[200000][18],height[200000],node[200000];
int depth[200000],disc[200000],fin[200000],inv[200000],num = 0;
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,height[u] = 0,node[u] = u;
    depth[u] = d,disc[u] = num++,inv[num-1] = u;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            doDFS(v,u,d+1);
            if (height[v]+1 > height[u]) {
                height[u] = height[v]+1,node[u] = node[v];
                if (!(height[u] & 1)) node[u] = parent[node[u]][0];
            }
        }
    }
    fin[u] = num;
    return 0;
}
int moveToward(int u,int v) {
    if (u == -1) return 0;
    if ((disc[v] >= disc[u]) && (disc[v] < fin[u])) {
        int i;
        for (i = logn-1; i >= 0; i--) {
            if ((parent[v][i] != -1) && (depth[parent[v][i]] > depth[u])) v = parent[v][i];
        }
        return v;
    }
    else return parent[u][0];
}
int height2[200000],node2[200000];
int doDFS2(int u,int p) {
    int i;
    int m1 = height2[u],m2 = height2[u],p1 = u,p2 = u;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            if (height[v]+1 >= m1) m2 = m1,p2 = p1,m1 = height[v]+1,p1 = v;
            else if (height[v]+1 >= m2) m2 = height[v]+1,p2 = v;
        }
    }
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            if (v == p1) height2[v] = m2+1,node2[v] = (p2 == u) ? node2[p2]:node[p2];
            else height2[v] = m1+1,node2[v] = (p1 == u) ? node2[p1]:node[p1];
            if (height2[v] & 1) node2[v] = moveToward(node2[v],v);
            doDFS2(v,u);
        }
    }
    return 0;
}
vpii cand,queries[200000];
int mm[400000];
int tree[400000],lazy[400000];
int apply(int p,int num) {
    tree[p] += num;
    if (p < N) lazy[p] += num;
    return 0;
}
int build(int p) {
    while (p > 1) p >>= 1,tree[p] = max(tree[p << 1],tree[(p << 1) | 1])+lazy[p];
    return 0;
}
int push(int p) {
    int i;
    for (i = logn-1; i > 0; i--) {
        int j = p >> i;
        if (lazy[j] != 0) {
            apply(j << 1,lazy[j]);
            apply((j << 1) | 1,lazy[j]);
            lazy[j] = 0;
        }
    }
    return 0;
}
int update(int as,int ae,int num) {
    as += N,ae += N+1;
    int oas = as,oae = ae;
    while (as < ae) {
        if (as & 1) apply(as++,num);
        if (ae & 1) apply(--ae,num);
        as >>= 1,ae >>= 1;
    }
    build(oas),build(oae-1);
    return 0;
}
int query(int qs,int qe) {
    qs += N,qe += N+1;
    push(qs),push(qe-1);
    int ans = 0;
    while (qs < qe) {
        if (qs & 1) ans = max(ans,tree[qs++]);
        if (qe & 1) ans = max(ans,tree[--qe]);
        qs >>= 1,qe >>= 1;
    }
    return ans;
}
/*
int prop(int s,int e,int i) {
    tree[i] += lazy[i];
    if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
    lazy[i] = 0;
    return 0;
}
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = depth[inv[s]];
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(build(s,mid,2*i+1),build(mid+1,e,2*i+2));
    return tree[i];
}
int update(int s,int e,int as,int ae,int i,int num) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return tree[i];
    else if ((s >= as) && (e <= ae)) {
        lazy[i] += num;
        prop(s,e,i);
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(update(s,mid,as,ae,2*i+1,num),update(mid+1,e,as,ae,2*i+2,num));
    return tree[i];
}
int query(int s,int e,int qs,int qe,int i) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return 0;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
*/
int doDFS3(int u,int p) {
    int i;
    for (i = 0; i < queries[u].size(); i++) {
        int v = queries[u][i].first;
        mm[queries[u][i].second] -= query(disc[v],disc[v]);
        if ((disc[u] >= disc[v]) && (disc[u] < fin[v])) {
            v = moveToward(v,u);
            mm[queries[u][i].second] += query(disc[v],fin[v]-1);
        }
        else {
            int m = query(fin[v],N-1);
            if (m >= -mm[queries[u][i].second]) mm[queries[u][i].second] = 0;
            else mm[queries[u][i].second] += max(m,query(0,disc[v]-1));
        }
    }
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            update(0,N-1,1),update(disc[v],fin[v]-1,-2);
            doDFS3(v,u);
            update(0,N-1,-1),update(disc[v],fin[v]-1,2);
        }
    }
    return 0;
}
int c[200000],n = 0;
vi tree2[1 << 19];
int ans[200000];
int add(int s,int e,int as,int ae,int i,int num) {
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        tree2[i].pb(num);
        return 0;
    }

    int mid = (s+e) / 2;
    add(s,mid,as,ae,2*i+1,num),add(mid+1,e,as,ae,2*i+2,num);
    return 0;
}
int process(int s,int e,int i) {
    if (s == e) {
        int j;
        for (j = 0; j < tree2[i].size(); j++) {
            if (c[tree2[i][j]] == 0) n++;
            c[tree2[i][j]]++;
        }
        ans[inv[s]] = n;
        for (j = 0; j < tree2[i].size(); j++) {
            if (c[tree2[i][j]] == 1) n--;
            c[tree2[i][j]]--;
        }
        return 0;
    }

    int j,mid = (s+e) / 2;
    for (j = 0; j < tree2[i].size(); j++) {
        if (c[tree2[i][j]] == 0) n++;
        c[tree2[i][j]]++;
    }
    process(s,mid,2*i+1),process(mid+1,e,2*i+2);
    for (j = 0; j < tree2[i].size(); j++) {
        if (c[tree2[i][j]] == 1) n--;
        c[tree2[i][j]]--;
    }
    return 0;
}
int main() {
    int i;
    int M,A,B;
    scanf("%d %d",&N,&M);
    for (i = 0; i < N-1; i++) {
        scanf("%d %d",&A,&B);
        A--,B--;
        adjList[A].pb(B);
        adjList[B].pb(A);
    }
    for (i = 0; i < N; i++) scanf("%d",&C[i]),C[i]--;

    int j;
    doDFS(0,-1,0);
    for (i = 1; (1 << i) < N; i++) {
        for (j = 0; j < N; j++) {
            if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
            else parent[j][i] = -1;
        }
    }
    logn = i;
    height2[0] = 0,node2[0] = -1;
    doDFS2(0,-1);
    for (i = 1; i < N; i++) {
        cand.pb(mp(parent[i][0],node[i]));
        cand.pb(mp(i,node2[i]));
    }
    for (i = 0; i < cand.size(); i++) queries[cand[i].second].pb(mp(cand[i].first,i));
    for (i = 0; i < N; i++) {
        i++,i--;
        tree[i+N] = depth[inv[i]];
    }
    for (i = N-1; i > 0; i--) tree[i] = max(tree[i << 1],tree[(i << 1) | 1]);
    doDFS3(0,-1);
    for (i = 0; i < cand.size(); i++) {
        if (mm[i] < 0) {
            int u = cand[i].first,v = cand[i].second;
            if ((disc[u] >= disc[v]) && (disc[u] < fin[v])) {
                v = moveToward(v,u);
                add(0,N-1,fin[v],N-1,0,C[u]),add(0,N-1,0,disc[v]-1,0,C[u]);
            }
            else add(0,N-1,disc[v],fin[v]-1,0,C[u]);
        }
    }
    process(0,N-1,0);
    for (i = 0; i < N; i++) printf("%d\n",ans[i]);

    return 0;
}

Compilation message

joi2019_ho_t5.cpp: In function 'int doDFS(int, int, int)':
joi2019_ho_t5.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int doDFS2(int, int)':
joi2019_ho_t5.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int doDFS3(int, int)':
joi2019_ho_t5.cpp:202:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < queries[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:215:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int process(int, int, int)':
joi2019_ho_t5.cpp:242:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < tree2[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:247:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < tree2[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:255:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < tree2[i].size(); j++) {
                 ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:260:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < tree2[i].size(); j++) {
                 ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:293:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < cand.size(); i++) queries[cand[i].second].pb(mp(cand[i].first,i));
                 ~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp:300:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < cand.size(); i++) {
                 ~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp:269:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:271:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&A,&B);
         ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:276:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&C[i]),C[i]--;
                             ~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 22136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 442 ms 48236 KB Output is correct
2 Correct 1182 ms 69064 KB Output is correct
3 Correct 141 ms 30064 KB Output is correct
4 Correct 882 ms 67292 KB Output is correct
5 Correct 1649 ms 98112 KB Output is correct
6 Correct 1160 ms 81496 KB Output is correct
7 Correct 758 ms 67352 KB Output is correct
8 Correct 838 ms 69132 KB Output is correct
9 Correct 849 ms 68560 KB Output is correct
10 Correct 865 ms 68604 KB Output is correct
11 Correct 676 ms 71936 KB Output is correct
12 Correct 1446 ms 89720 KB Output is correct
13 Correct 1216 ms 83152 KB Output is correct
14 Correct 1210 ms 81688 KB Output is correct
15 Correct 783 ms 71896 KB Output is correct
16 Correct 1307 ms 95216 KB Output is correct
17 Correct 1110 ms 81324 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 663 ms 58452 KB Output is correct
2 Correct 1547 ms 99196 KB Output is correct
3 Correct 127 ms 31452 KB Output is correct
4 Correct 804 ms 67932 KB Output is correct
5 Correct 1482 ms 98864 KB Output is correct
6 Correct 1180 ms 79656 KB Output is correct
7 Correct 777 ms 68120 KB Output is correct
8 Correct 934 ms 71528 KB Output is correct
9 Correct 885 ms 70624 KB Output is correct
10 Correct 1000 ms 69660 KB Output is correct
11 Correct 759 ms 69404 KB Output is correct
12 Correct 1485 ms 98396 KB Output is correct
13 Correct 1096 ms 80992 KB Output is correct
14 Correct 1082 ms 82016 KB Output is correct
15 Correct 651 ms 71908 KB Output is correct
16 Correct 1231 ms 98016 KB Output is correct
17 Correct 1034 ms 79964 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 22136 KB Output isn't correct
2 Halted 0 ms 0 KB -