Submission #765162

#	Time	Username	Problem	Language	Result	Execution time	Memory
765162		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	47 / 100	1062 ms	9880 KiB

roadsideadverts

//Bismillahir-Rahmanir-Rahim

# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
# define pii pair <int, int>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 5e4 + 2;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
const ll P = 67;

using namespace std;

int n, q, timer;
vector <pii> g[maxn];
int uu[maxn], vv[maxn], ww[maxn];
int tin[maxn], d[maxn];
int sz[maxn], mx[maxn];
int par[maxn], st[maxn];

void dfs (int v = 1, int pa = 1)
{
    sz[v] = 1, mx[v] = -1;
    for (pii it : g[v])
    {
        int to = it.ff, w = it.ss;
        if (to == pa) continue;
        dfs(to, v);
        sz[v] += sz[to];
        if (mx[v] == -1 || sz[mx[v]] < sz[to])
            mx[v] = to;
    }
}

void hld (int v = 1, int pa = 1)
{
    tin[v] = ++timer;
    par[v] = pa;
    d[v] = d[pa] + 1;
    if (mx[v] != -1)
    {
        st[mx[v]] = st[v];
        hld(mx[v], v);
    }
    for (pii it : g[v])
    {
        int to = it.ff, w = it.ss;
        if (to == pa || to == mx[v]) continue;
        st[to] = to;
        hld(to, v);
    }
}

struct segtree 
{
    int t[maxn * 4], z[maxn * 4];
    void build (int v = 1, int tl = 1, int tr = n)
    {
        t[v] = 0, z[v] = -1;
        if (tl == tr)
        {
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
    }
    void push (int v, int tl, int tr)
    {
        if (z[v] != -1 && tl != tr)
        {
            t[v * 2] = t[v * 2 + 1] = z[v];
            z[v * 2] = z[v * 2 + 1] = z[v];
        } 
    }
    void update (int l, int r, int v = 1, int tl = 1, int tr = n)
    {
        push(v, tl, tr);
        if (tr < l || r < tl) return;
        if (l <= tl && tr <= r)
        {
            t[v] = 1;
            z[v] = 1;
            return;
        }
        int tm = (tl + tr) >> 1;
        update(l, r, v * 2, tl, tm);
        update(l, r, v * 2 + 1, tm + 1, tr);
    }
    int get (int pos, int v = 1, int tl = 1, int tr = n)
    {
        push(v, tl, tr);
        if (tl == tr)
        {
            return t[v];
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm)
        {
            return get(pos, v * 2, tl, tm);
        }
        else
        {
            return get(pos, v * 2 + 1, tm + 1, tr);
        }
    }
} t;

int lca (int u, int v)
{
    while (1)
    {
        int x = st[u], y = st[v];
        if (x == y)
        {
            if (tin[u] < tin[v])
            {
                return u;
            }
            else
            {
                return v;
            }
        }
        else if (d[x] >= d[y])
        {
            u = par[x];
        }
        else
        {
            v = par[y];
        }
    }
    return -1;
}

void upd (int u, int v)
{
    while (1)
    {
        int x = st[u], y = st[v];
        if (x == y)
        {
            int l = min(tin[u], tin[v]);
            int r = max(tin[u], tin[v]);
            t.update(l + 1, r);
            break;
        }
        if (d[x] >= d[y])
        {
            int l = min(tin[u], tin[x]);
            int r = max(tin[u], tin[x]);
            t.update(l, r);
            u = par[x];
        }
        else
        {
            int l = min(tin[y], tin[v]);
            int r = max(tin[y], tin[v]);
            t.update(l, r);
            v = par[y];
        }
    }
}

void ma1n (/* SABR */)
{
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        cin >> uu[i] >> vv[i] >> ww[i];
        uu[i]++, vv[i]++;
        g[uu[i]].pb({vv[i], ww[i]});
        g[vv[i]].pb({uu[i], ww[i]});
    }
    dfs ();
    hld ();
    cin >> q;
    while (q--)
    {
        vector <int> x(5);
        t.build();
        for (int &a : x)
        {
            cin >> a;
            a++;
        }
        int lc = lca(x[0], x[1]);
        for (int i = 2; i < 5; ++i)
        {
            lc = lca(lc, x[i]);
        }
        for (int i = 0; i < 5; ++i)
        {
            upd(x[i], lc);
        }
        int res = 0;
        for (int i = 1; i < n; ++i)
        {
            if (uu[i] == par[vv[i]])
            {
                if (t.get(tin[vv[i]]))
                {
                    res += ww[i];
                }
            }
            else
            {
                if (t.get(tin[uu[i]]))
                {
                    res += ww[i];
                }
            }
        }
        cout << res << nl;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << '\n';
        ma1n();
    }
    return 0;
}

// 998batrr | BbIWEJI 3A TObOU!!!
// tourist  | BbIWEJI 3A TObOU!!!

Compilation message (stderr)

roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:39:25: warning: unused variable 'w' [-Wunused-variable]
   39 |         int to = it.ff, w = it.ss;
      |                         ^
roadsideadverts.cpp: In function 'void hld(int, int)':
roadsideadverts.cpp:60:25: warning: unused variable 'w' [-Wunused-variable]
   60 |         int to = it.ff, w = it.ss;
      |                         ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 40 / 40
• Subtask 4: 0 / 30