Submission #1113259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113259		fern	Grapevine (NOI22_grapevine)	C++17	100 / 100	729 ms	106884 KiB

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 (stderr)

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 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32