oj.uz

Submission #764842

# Submission time Handle Problem Language Result Execution time Memory
764842 2023-06-24T05:39:59 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
70 / 100
 1000 ms 28920 KB 
#include "bits/stdc++.h"
using namespace std;

// #define ORD_SET
// #define ROPE
#ifdef ORD_SET
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template<typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#ifdef ROPE
    #include <ext/rope>
    using namespace __gnu_cxx;
#endif        

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
void ioigold2024insh() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void pre(ll a) { cout<<fixed<<setprecision(a); }
ll bit(ll a) { return __builtin_popcountll(a); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ld rnd() { return rng()%INT_MAX*1.0/INT_MAX; }

struct sn { ll l, r, x; };
const ll mod = 1e9+7, inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll N = 3e5+5;
ll up[N][20], d[N], pr[N], e[N];
vector<pair<ll, ll>> g[N];
vector<pair<ll, ll>> v;
map<pair<ll, ll>, ll> edge;
ll mm, root;

void dfs(ll v, ll p, ll t) {
    up[v][0] = p, d[v] = d[p]+1;
    if(d[v]>mm) mm = d[v], root = v;
    for(ll i=1; i<=16; i++) up[v][i] = up[up[v][i-1]][i-1];
    for(auto [to, w]: g[v]) {
        if(to==p) continue;
        dfs(to, v, t);
        if(t) pr[d[to]] = w;
        else pr[to] = w;
    }
}

ll lca(ll x, ll y) {
    if(d[x]<d[y]) swap(x, y);
    ll k = d[x]-d[y];
    for(ll i=16; i>=0; i--) {
        if(k&(1<<i)) x = up[x][i];
    }
    if(x==y) return x;
    for(ll i=16; i>=0; i--) {
        if(up[x][i]!=up[y][i]) x = up[x][i], y = up[y][i];
    }
    return up[x][0];
}

void kigash() {
    ll n, mx = 0;
    cin>>n;
    for(ll i=1; i<n; i++) {
        ll u, v, w;
        cin>>u>>v>>w, u++, v++;
        g[u].pb({v, w});
        g[v].pb({u, w});
        mx = max({mx, sz(g[u]), sz(g[v])});
        edge[{u, v}] = edge[{v, u}] = w;
    }
    dfs(1, 0, 0);
    if(mx<=2) dfs(root, 0, 1);
    if(mx<=2) {
        ll q; cin>>q;
        for(ll i=1; i<=n; i++) pr[i] += pr[i-1];
        for(ll i=1; i<=q; i++) {
            ll x, res = 0; cin>>x, x++;
            vector<pair<ll, ll>> v;
            for(ll j=1; j<=4; j++) {
                ll y; cin>>y, y++;
                ll l = min(d[x], d[y]), r = max(d[x], d[y]);
                v.pb({l, r});
            }
            sort(all(v));
            ll l = v[0].ff, r = v[0].ss;
            for(ll j=1; j<4; j++) {
                if(v[j].ff>r) res += pr[r]-pr[l], l = v[j].ff, r = v[j].ss;
                else r = v[j].ss;
            }
            res += pr[r]-pr[l];
            cout<<res<<"\n";
        }
        return;
    }
    ll q;
    cin>>q;
    for(ll i=1; i<=q; i++) {
        ll x, res = 0; cin>>x, x++;
        vector<ll> v;
        for(ll j=1; j<=4; j++) {
            ll y; cin>>y, y++;
            v.pb(y);
            ll lc = lca(x, y);
            while(1) {
                if(y==lc) break;
                if(!e[y]) {
                    res += pr[y];
                    e[y] = 1;
                }
                y = up[y][0];
            }
            ll x1 = x;
            while(1) {
                if(x==lc) break;
                if(!e[x]) {
                    res += pr[x];
                    e[x] = 1;
                }
                x = up[x][0];
            }
            x = x1;
        }
        for(ll j=1; j<=4; j++) {
            ll y = v[j-1];
            ll lc = lca(x, y);
            while(1) {
                if(y==lc) break;
                e[y] = 0;
                y = up[y][0];
            }
            ll x1 = x;
            while(1) {
                if(x==lc) break;
                e[x] = 0;
                x = up[x][0];
            }
            x = x1;
        }
        cout<<res<<"\n";
    }
    return;
}

signed main(/*Kigash Amir*/) {
    // freopen("");
    ioigold2024insh();
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) kigash();
    exit(0);
}

Compilation message

roadsideadverts.cpp: In function 'void freopen(std::string)':
roadsideadverts.cpp:31:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:31:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 28480 KB Output is correct
2 Correct 82 ms 28696 KB Output is correct
3 Correct 79 ms 28712 KB Output is correct
4 Correct 80 ms 28748 KB Output is correct
5 Correct 99 ms 28876 KB Output is correct
6 Correct 81 ms 28820 KB Output is correct
7 Correct 85 ms 28796 KB Output is correct
8 Correct 79 ms 28812 KB Output is correct
9 Correct 106 ms 28784 KB Output is correct
10 Correct 92 ms 28920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25092 KB Output is correct
2 Correct 251 ms 28440 KB Output is correct
3 Correct 266 ms 28476 KB Output is correct
4 Correct 259 ms 28460 KB Output is correct
5 Correct 252 ms 28364 KB Output is correct
6 Correct 268 ms 28484 KB Output is correct
7 Correct 258 ms 28480 KB Output is correct
8 Correct 252 ms 28464 KB Output is correct
9 Correct 276 ms 28544 KB Output is correct
10 Correct 259 ms 28472 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 82 ms 28480 KB Output is correct
3 Correct 82 ms 28696 KB Output is correct
4 Correct 79 ms 28712 KB Output is correct
5 Correct 80 ms 28748 KB Output is correct
6 Correct 99 ms 28876 KB Output is correct
7 Correct 81 ms 28820 KB Output is correct
8 Correct 85 ms 28796 KB Output is correct
9 Correct 79 ms 28812 KB Output is correct
10 Correct 106 ms 28784 KB Output is correct
11 Correct 92 ms 28920 KB Output is correct
12 Correct 53 ms 25092 KB Output is correct
13 Correct 251 ms 28440 KB Output is correct
14 Correct 266 ms 28476 KB Output is correct
15 Correct 259 ms 28460 KB Output is correct
16 Correct 252 ms 28364 KB Output is correct
17 Correct 268 ms 28484 KB Output is correct
18 Correct 258 ms 28480 KB Output is correct
19 Correct 252 ms 28464 KB Output is correct
20 Correct 276 ms 28544 KB Output is correct
21 Correct 259 ms 28472 KB Output is correct
22 Correct 75 ms 28484 KB Output is correct
23 Correct 74 ms 25168 KB Output is correct
24 Execution timed out 1096 ms 28364 KB Time limit exceeded
25 Halted 0 ms 0 KB -