답안 #1113259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113259	2024-11-16T09:02:16 Z	fern	Grapevine (NOI22_grapevine)	C++17	100 / 100	729 ms	106884 KB

Main

/*
 *|---------------------------------------------|*
 *|       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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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