답안 #764829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764829 2023-06-24T05:31:09 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
1000 ms 32588 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];
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) {
    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), pr[d[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);
    dfs(root, 0);
    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++) {
        map<pair<ll, ll>, ll> e;
        ll x, res = 0; cin>>x, x++;
        for(ll j=1; j<=4; j++) {
            ll y; cin>>y, y++;
            ll lc = lca(x, y);
            while(1) {
                if(y==lc) break;
                if(!e.count({y, up[y][0]})) {
                    res += edge[{y, up[y][0]}];
                    e[{y, up[y][0]}] = e[{up[y][0], y}] = 1;
                }
                y = up[y][0];
            }
            while(1) {
                if(x==lc) break;
                if(!e.count({x, up[x][0]})) {
                    res += edge[{x, up[x][0]}];
                    e[{x, up[x][0]}] = e[{up[x][0], x}] = 1;
                }
                x = up[x][0];
            }
        }
        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); }
      |                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 28476 KB Output is correct
2 Correct 79 ms 28712 KB Output is correct
3 Correct 78 ms 28712 KB Output is correct
4 Correct 97 ms 28856 KB Output is correct
5 Correct 80 ms 28784 KB Output is correct
6 Correct 78 ms 28708 KB Output is correct
7 Correct 77 ms 28736 KB Output is correct
8 Correct 81 ms 28780 KB Output is correct
9 Correct 95 ms 28744 KB Output is correct
10 Correct 78 ms 28748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 24396 KB Output is correct
2 Execution timed out 1082 ms 32588 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 69 ms 28476 KB Output is correct
3 Correct 79 ms 28712 KB Output is correct
4 Correct 78 ms 28712 KB Output is correct
5 Correct 97 ms 28856 KB Output is correct
6 Correct 80 ms 28784 KB Output is correct
7 Correct 78 ms 28708 KB Output is correct
8 Correct 77 ms 28736 KB Output is correct
9 Correct 81 ms 28780 KB Output is correct
10 Correct 95 ms 28744 KB Output is correct
11 Correct 78 ms 28748 KB Output is correct
12 Correct 61 ms 24396 KB Output is correct
13 Execution timed out 1082 ms 32588 KB Time limit exceeded
14 Halted 0 ms 0 KB -