제출 #765321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765321		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	44 ms	11384 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>
# define all(x) (x).begin(), (x).end()
 
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, d[maxn], timer;
int tin[maxn], tout[maxn];
vector <pii> g[maxn];
int up[maxn][18];

void dfs (int v = 1, int pa = 1)
{
    up[v][0] = pa;
    for (int j = 1; j <= 16; ++j)
    {
        up[v][j] = up[up[v][j - 1]][j - 1];
    }
    tin[v] = ++timer;
    for (pii it : g[v])
    {
        int to = it.ff, w = it.ss;
        if (to == pa) continue;
        d[to] = d[v] + w;
        dfs(to, v);
    }
    tout[v] = timer;
}

bool anc (int u, int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca (int u, int v)
{
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    for (int j = 16; j >= 0; --j)
    {
        if (!anc(up[u][j], v))
        {
            u = up[u][j];
        }
    }
    return up[u][0];
}

int dist (int x, int y)
{
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

void ma1n (/* SABR */)
{
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dfs ();
    cin >> q;
    while (q--)
    {
        vector <pair <int, int> > x(5);
        for (int i = 0; i < 5; ++i)
        {
            cin >> x[i].ss;
            x[i].ss++;
            x[i].ff = tin[x[i].ss];
        }
        sort(all(x));
        int ans = 0;
        for (int i = 0; i < 5; ++i)
        {
            int nxt = (i + 1) % 5;
            int lc = lca(x[i].ss, x[nxt].ss);
            ans += dist(x[i].ss, x[nxt].ss);
        }
        cout << ans / 2 << 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!!!

컴파일 시 표준 에러 (stderr) 메시지

roadsideadverts.cpp: In function 'void ma1n()':
roadsideadverts.cpp:102:17: warning: unused variable 'lc' [-Wunused-variable]
  102 |             int lc = lca(x[i].ss, x[nxt].ss);
      |                 ^~

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