oj.uz

Submission #1113259

# Submission time Handle Problem Language Result Execution time Memory
1113259 2024-11-16T09:02:16 Z fern Grapevine (NOI22_grapevine) C++17
100 / 100
 729 ms 106884 KB 
/*
 *|---------------------------------------------|*
 *|       Author  : Le Hoang An                 |*
 *|     From  :  Bien Hoa Giftd High School     |*
 *|---------------------------------------------|*
 *|    DEBUGGING IS TWICE AS HARD AS CODING.    |*
 *|    IF YOU WRITE CODE THAT IS TOO SMART,     |*
 *|    YOU WON’T BE SMART ENOUGH TO DEBUG IT.   |*
 *|---------------------------------------------|*
*/
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3fLL
#define faster                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                     \
    cout.tie(NULL);
#define MCI signed main()
using namespace std;
//#define int long long
#define K   16
typedef long long ll;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn=100002;
const int mod=1000000007;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
    bool maximize(X &x, const Y&y)
    {
        if(x<y)
        {
            x=y;
            return true;
        }
        else return false;
    }
template <class X, class Y>
    bool minimize(X &x, const Y&y)
    {
        if(x>y)
        {
            x=y;
            return true;
        }
        else return false;
    }

void file()
{
      #define TASK "Fern"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
}
unsigned int X = 12345;
 
int rand_() {
    return (X *= 3) >> 1;
}
int n;
int ii[maxn - 1], jj[maxn - 1], ww[maxn - 1], hh[maxn - 1];
void sort(int *hh, int l, int r) {
    while (l < r) {
        int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
 
        while (j < k) {
            int c = ii[hh[j]] != ii[h] ? ii[hh[j]] - ii[h] : jj[hh[j]] - jj[h];
 
            if (c == 0)
                j++;
            else if (c < 0) {
                tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
                i++, j++;
            } else {
                k--;
                tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
            }
        }
        sort(hh, l, i);
        l = k;
    }
}
int search(int i, int j) {
    int lower = -1, upper = n - 1;
 
    while (upper - lower > 1) {
        int h = (lower + upper) / 2;
 
        if (ii[hh[h]] < i || ii[hh[h]] == i && jj[hh[h]] <= j)
            lower = h;
        else
            upper = h;
    }
    return hh[lower];
}
 
int *ej[maxn], eo[maxn];
int sz[maxn];
int uu[maxn][K + 1], ta[maxn][K + 1], tb[maxn][K + 1], kk[maxn];
long long *ss[maxn], *pp[maxn]; int nn_[maxn];
int n_, c, t;
 
void append(int i, int j) {
    int o = eo[i]++;
 
    if (o >= 2 && (o & o - 1) == 0)
        ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
    ej[i][o] = j;
}
 
void del(int i, int j) {
    int o;
 
    for (o = eo[i]; o--; )
        if (ej[i][o] == j) {
            eo[i]--;
            while (o < eo[i])
                ej[i][o] = ej[i][o + 1], o++;
            return;
        }
}
 
void dfs1(int p, int i) {
    int o, centroid;
 
    sz[i] = 1, centroid = 1;
    for (o = eo[i]; o--; ) {
        int j = ej[i][o];
 
        if (j != p) {
            dfs1(i, j);
            sz[i] += sz[j];
            if (sz[j] * 2 > n_)
                centroid = 0;
        }
    }
    if ((n_ - sz[i]) * 2 > n_)
        centroid = 0;
    if (centroid)
        c = i;
}
 
void dfs2(int p, int i, int k, int u) {
    int o;
 
    uu[i][k] = u;
    ta[i][k] = t++;
    for (o = eo[i]; o--; ) {
        int j = ej[i][o];
 
        if (j != p)
            dfs2(i, j, k, u);
    }
    tb[i][k] = t;
}
 
void cd(int n, int i, int k) {
    int o;
 
    n_ = n, dfs1(-1, i), i = c;
    kk[i] = k;
    t = 0, dfs2(-1, i, k, i);
    nn_[i] = 1;
    while (nn_[i] <= n)
        nn_[i] <<= 1;
    ss[i] = (long long *) malloc(nn_[i] * 2 * sizeof *ss[i]);
    pp[i] = (long long *) malloc(nn_[i] * 2 * sizeof *pp[i]);
    memset(ss[i], 0, nn_[i] * 2 * sizeof *ss[i]);
    memset(pp[i], 0x3f, nn_[i] * 2 * sizeof *pp[i]);
    for (o = eo[i]; o--; ) {
        int j = ej[i][o];
 
        del(j, i);
        cd(sz[j] < sz[i] ? sz[j] : n - sz[i], j, k + 1);
    }
}
 
void pul(int u, int i) {
    int l = i << 1, r = l | 1;
 
    ss[u][i] = ss[u][l] + ss[u][r];
    pp[u][i] = min(pp[u][l], pp[u][r] == INF ? INF : ss[u][l] + pp[u][r]);
}
 
void add_(int u, int i, int x) {
    i += nn_[u];
    ss[u][i] += x, pp[u][i] = pp[u][i] == INF ? INF : ss[u][i];
    while (i > 1)
        pul(u, i >>= 1);
}
 
void toggle_(int u, int i) {
    i += nn_[u];
    pp[u][i] = pp[u][i] == INF ? ss[u][i] : INF;
    while (i > 1)
        pul(u, i >>= 1);
}
 
long long query_(int u, int r) {
    int l;
    long long s;
 
    l = 0, s = 0;
    for (l += nn_[u], r += nn_[u]; l <= r; l >>= 1, r >>= 1)
        if ((r & 1) == 0)
            s += ss[u][r--];
    return s;
}
 
void add(int i, int j, int x) {
    int k, u, tmp;
 
    for (k = min(kk[i], kk[j]); k >= 0; k--) {
        u = uu[i][k];
        if (ta[i][k] > ta[j][k])
            tmp = i, i = j, j = tmp;
        add_(u, ta[j][k], x), add_(u, tb[j][k], -x);
    }
}
 
void toggle(int i) {
    int k, u;
 
    for (k = kk[i]; k >= 0; k--) {
        u = uu[i][k];
        toggle_(u, ta[i][k]);
    }
}
 
long long query(int i) {
    int k, u;
    long long ans;
 
    ans = INF;
    for (k = kk[i]; k >= 0; k--) {
        u = uu[i][k];
        ans = min(ans, query_(u, ta[i][k]) + pp[u][1]);
    }
    if (ans == INF)
        ans = -1;
    return ans;
}
MCI
{
    faster;
    file();
    int q, h, i, j, tmp;
 
    cin>>n>>q;
    for (i = 0; i < n; i++)
        ej[i] = (int *) malloc(2 * sizeof *ej[i]);
    for (h = 0; h < n - 1; h++) {
        cin>>i>>j>>ww[h];
        i--, j--;
        if (i > j)
            tmp = i, i = j, j = tmp;
        ii[h] = i, jj[h] = j;
        append(i, j), append(j, i);
    }
    for (h = 0; h < n - 1; h++)
        hh[h] = h;
    sort(hh, 0, n - 1);
    cd(n, 0, 0);
    for (h = 0; h < n - 1; h++)
        add(ii[h], jj[h], ww[h]);
    while (q--) {
        int t, w;
 
        cin>>t;
        if (t == 1) {
            cin>>i, i--;
            cout<<query(i); el
        } else if (t == 2) {
            cin>>i, i--;
            toggle(i);
        } else {
            cin>>i>>j>>w, i--, j--;
            if (i > j)
                tmp = i, i = j, j = tmp;
            h = search(i, j);
            add(ii[h], jj[h], w - ww[h]);
            ww[h] = w;
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int search(int, int)':
Main.cpp:106:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  106 |         if (ii[hh[h]] < i || ii[hh[h]] == i && jj[hh[h]] <= j)
      |                              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void append(int, int)':
Main.cpp:123:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  123 |     if (o >= 2 && (o & o - 1) == 0)
      |                        ~~^~~
Main.cpp: In function 'void file()':
Main.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1872 KB Output is correct
2 Correct 5 ms 1884 KB Output is correct
3 Correct 5 ms 1872 KB Output is correct
4 Correct 5 ms 1872 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Correct 5 ms 1916 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 2 ms 1360 KB Output is correct
9 Correct 3 ms 1360 KB Output is correct
10 Correct 7 ms 2128 KB Output is correct
11 Correct 5 ms 1872 KB Output is correct
12 Correct 5 ms 2128 KB Output is correct
13 Correct 3 ms 1360 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 86856 KB Output is correct
2 Correct 590 ms 87396 KB Output is correct
3 Correct 680 ms 85716 KB Output is correct
4 Correct 522 ms 106184 KB Output is correct
5 Correct 564 ms 98960 KB Output is correct
6 Correct 567 ms 102248 KB Output is correct
7 Correct 136 ms 44660 KB Output is correct
8 Correct 123 ms 43848 KB Output is correct
9 Correct 132 ms 43848 KB Output is correct
10 Correct 486 ms 102728 KB Output is correct
11 Correct 470 ms 101884 KB Output is correct
12 Correct 486 ms 104336 KB Output is correct
13 Correct 115 ms 44104 KB Output is correct
14 Correct 126 ms 43872 KB Output is correct
15 Correct 132 ms 44612 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 83024 KB Output is correct
2 Correct 587 ms 83016 KB Output is correct
3 Correct 616 ms 85372 KB Output is correct
4 Correct 596 ms 80968 KB Output is correct
5 Correct 556 ms 84772 KB Output is correct
6 Correct 520 ms 83832 KB Output is correct
7 Correct 506 ms 83784 KB Output is correct
8 Correct 506 ms 85612 KB Output is correct
9 Correct 544 ms 83752 KB Output is correct
10 Correct 537 ms 86572 KB Output is correct
11 Correct 569 ms 84280 KB Output is correct
12 Correct 595 ms 83076 KB Output is correct
13 Correct 550 ms 86028 KB Output is correct
14 Correct 531 ms 83016 KB Output is correct
15 Correct 592 ms 84300 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 84368 KB Output is correct
2 Correct 724 ms 87556 KB Output is correct
3 Correct 666 ms 85364 KB Output is correct
4 Correct 574 ms 106884 KB Output is correct
5 Correct 576 ms 102468 KB Output is correct
6 Correct 560 ms 103488 KB Output is correct
7 Correct 139 ms 44380 KB Output is correct
8 Correct 146 ms 45384 KB Output is correct
9 Correct 141 ms 44616 KB Output is correct
10 Correct 517 ms 104704 KB Output is correct
11 Correct 498 ms 100772 KB Output is correct
12 Correct 463 ms 105168 KB Output is correct
13 Correct 131 ms 44112 KB Output is correct
14 Correct 128 ms 45608 KB Output is correct
15 Correct 123 ms 44768 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 86856 KB Output is correct
2 Correct 707 ms 89016 KB Output is correct
3 Correct 706 ms 86724 KB Output is correct
4 Correct 586 ms 100424 KB Output is correct
5 Correct 525 ms 106824 KB Output is correct
6 Correct 562 ms 102468 KB Output is correct
7 Correct 171 ms 44104 KB Output is correct
8 Correct 152 ms 44616 KB Output is correct
9 Correct 144 ms 44872 KB Output is correct
10 Correct 530 ms 98944 KB Output is correct
11 Correct 517 ms 102212 KB Output is correct
12 Correct 543 ms 97216 KB Output is correct
13 Correct 144 ms 44832 KB Output is correct
14 Correct 135 ms 44264 KB Output is correct
15 Correct 159 ms 44216 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1872 KB Output is correct
2 Correct 5 ms 1884 KB Output is correct
3 Correct 5 ms 1872 KB Output is correct
4 Correct 5 ms 1872 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Correct 5 ms 1916 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 2 ms 1360 KB Output is correct
9 Correct 3 ms 1360 KB Output is correct
10 Correct 7 ms 2128 KB Output is correct
11 Correct 5 ms 1872 KB Output is correct
12 Correct 5 ms 2128 KB Output is correct
13 Correct 3 ms 1360 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct
16 Correct 663 ms 86856 KB Output is correct
17 Correct 590 ms 87396 KB Output is correct
18 Correct 680 ms 85716 KB Output is correct
19 Correct 522 ms 106184 KB Output is correct
20 Correct 564 ms 98960 KB Output is correct
21 Correct 567 ms 102248 KB Output is correct
22 Correct 136 ms 44660 KB Output is correct
23 Correct 123 ms 43848 KB Output is correct
24 Correct 132 ms 43848 KB Output is correct
25 Correct 486 ms 102728 KB Output is correct
26 Correct 470 ms 101884 KB Output is correct
27 Correct 486 ms 104336 KB Output is correct
28 Correct 115 ms 44104 KB Output is correct
29 Correct 126 ms 43872 KB Output is correct
30 Correct 132 ms 44612 KB Output is correct
31 Correct 564 ms 83024 KB Output is correct
32 Correct 587 ms 83016 KB Output is correct
33 Correct 616 ms 85372 KB Output is correct
34 Correct 596 ms 80968 KB Output is correct
35 Correct 556 ms 84772 KB Output is correct
36 Correct 520 ms 83832 KB Output is correct
37 Correct 506 ms 83784 KB Output is correct
38 Correct 506 ms 85612 KB Output is correct
39 Correct 544 ms 83752 KB Output is correct
40 Correct 537 ms 86572 KB Output is correct
41 Correct 569 ms 84280 KB Output is correct
42 Correct 595 ms 83076 KB Output is correct
43 Correct 550 ms 86028 KB Output is correct
44 Correct 531 ms 83016 KB Output is correct
45 Correct 592 ms 84300 KB Output is correct
46 Correct 713 ms 84368 KB Output is correct
47 Correct 724 ms 87556 KB Output is correct
48 Correct 666 ms 85364 KB Output is correct
49 Correct 574 ms 106884 KB Output is correct
50 Correct 576 ms 102468 KB Output is correct
51 Correct 560 ms 103488 KB Output is correct
52 Correct 139 ms 44380 KB Output is correct
53 Correct 146 ms 45384 KB Output is correct
54 Correct 141 ms 44616 KB Output is correct
55 Correct 517 ms 104704 KB Output is correct
56 Correct 498 ms 100772 KB Output is correct
57 Correct 463 ms 105168 KB Output is correct
58 Correct 131 ms 44112 KB Output is correct
59 Correct 128 ms 45608 KB Output is correct
60 Correct 123 ms 44768 KB Output is correct
61 Correct 643 ms 86856 KB Output is correct
62 Correct 707 ms 89016 KB Output is correct
63 Correct 706 ms 86724 KB Output is correct
64 Correct 586 ms 100424 KB Output is correct
65 Correct 525 ms 106824 KB Output is correct
66 Correct 562 ms 102468 KB Output is correct
67 Correct 171 ms 44104 KB Output is correct
68 Correct 152 ms 44616 KB Output is correct
69 Correct 144 ms 44872 KB Output is correct
70 Correct 530 ms 98944 KB Output is correct
71 Correct 517 ms 102212 KB Output is correct
72 Correct 543 ms 97216 KB Output is correct
73 Correct 144 ms 44832 KB Output is correct
74 Correct 135 ms 44264 KB Output is correct
75 Correct 159 ms 44216 KB Output is correct
76 Correct 1 ms 336 KB Output is correct
77 Correct 1 ms 336 KB Output is correct
78 Correct 1 ms 336 KB Output is correct
79 Correct 729 ms 85576 KB Output is correct
80 Correct 697 ms 87928 KB Output is correct
81 Correct 695 ms 88124 KB Output is correct
82 Correct 526 ms 102348 KB Output is correct
83 Correct 490 ms 102728 KB Output is correct
84 Correct 516 ms 104164 KB Output is correct
85 Correct 123 ms 45640 KB Output is correct
86 Correct 131 ms 45128 KB Output is correct
87 Correct 140 ms 44200 KB Output is correct
88 Correct 497 ms 100168 KB Output is correct
89 Correct 528 ms 101192 KB Output is correct
90 Correct 548 ms 99572 KB Output is correct
91 Correct 147 ms 45388 KB Output is correct
92 Correct 149 ms 44480 KB Output is correct
93 Correct 123 ms 44128 KB Output is correct