oj.uz

Submission #764969

# Submission time Handle Problem Language Result Execution time Memory
764969 2023-06-24T07:03:08 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 15180 KB 
//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 up[maxn][17];
map <pii, int> mp;
bool used[maxn];
int ww[maxn];
int tin[maxn], tout[maxn];

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

void ma1n (/* SABR */)
{
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v >> ww[i];
        g[u].pb({v, ww[i]});
        g[v].pb({u, ww[i]});
        mp[{u, v}] = i;
        mp[{v, u}] = i;
    }
    dfs();
    cin >> q;
    while (q--)
    {
        vector <int> v(5);
        for (int i = 0; i < 5; ++i)
        {
            cin >> v[i];
        }
        int lc = lca(v[0], v[1]);
        for (int i = 0; i < 5; ++i)
        {
            for (int j = i + 1; j < 5; ++j)
            {
                lc = lca(lc, lca(v[i], v[j]));
            }
        }   
        memset(used, 0, sizeof used);
        int res = 0;
        for (int i = 0; i < 5; ++i)
        {
            int cur = v[i];
            while (cur != lc)
            {
                int id = mp[{cur, up[cur][0]}];
                if (!used[id])
                {
                    res += ww[id];
                    used[id] = 1;
                }
                cur = up[cur][0];
            }
        }
        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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 14500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13508 KB Output is correct
2 Execution timed out 1090 ms 15180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Execution timed out 1073 ms 14500 KB Time limit exceeded
3 Halted 0 ms 0 KB -