oj.uz

Submission #624403

# Submission time Handle Problem Language Result Execution time Memory
624403 2022-08-08T07:27:45 Z radal Designated Cities (JOI19_designated_cities) C++17
16 / 100
 303 ms 58776 KB 
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}

int par[N][20],h[N],r,U,V;
ll opt[N],d[N][2],up[N],sum;
pair<ll,int> mx[N];
vector<pair<int,pll>> adj[N];
void pre(int v,int p){
    par[v][0] = p;
    for (auto u : adj[v]){
        if (u.X == p) continue;
        h[u.X] = h[v]+1;
        d[u.X][0] = d[v][0]+u.Y.X;
        d[u.X][1] = d[v][1]+u.Y.Y;
        pre(u.X,v);
        up[v] += up[u.X]+u.Y.Y;
    }
}
void dfs(int v,int p){
    if (adj[v].size() == 1){
        mx[v] = {d[v][0],v};
        return;
    }
    ll a = -1,b = -1;
    pll pa = {-1,-1};
    for (auto u : adj[v]){
        if (u.X == p) continue;
        dfs(u.X,v);
        mx[v] = max(mx[v],mx[u.X]);
        if (mx[u.X].X > a){
            swap(pa.X,pa.Y);
            b = a;
            a = mx[u.X].X;
            pa.X = mx[u.X].Y;
        }
        else if (mx[u.X].X > b){
            b = mx[u.X].X;
            pa.Y = mx[u.X].Y;
        }
    }
    if (b == -1) return;
    ll calc = sum-up[r]+d[v][1]-d[v][0]-a-b+2*d[v][0];
    if (calc < opt[2]){
        opt[2] = calc;
        U = pa.X;
        V = pa.Y;
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    memset(opt,63,sizeof opt);
    int n;
    cin >> n;
    rep(i,1,n){
        int u,v,a,b;
        cin >> u >> v >> a >> b;
        adj[u].pb({v,{a,b}});
        adj[v].pb({u,{b,a}});
        sum += a;
        sum += b;
    }
    if (n == 2){
        int q;
        cin >> q;
        while (q--){
            int t;
            cin >> t;
            if (t == 2){
                cout << 0 << endl;
                continue;
            }
            if (t == 1){
                cout << min(adj[1][0].Y.Y,adj[1][0].Y.X) << endl;
                continue;
            }
        }
        return 0;
    }
    rep(i,1,n+1) if (adj[i].size() > 1) r = i;
    pre(r,0);
    rep(j,1,20){
        rep(i,1,n+1){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    rep(i,1,n+1){
        opt[1] = min(opt[1],sum-up[r]+d[i][1]-d[i][0]);
    }
    dfs(r,0);
    int q;
    cin >> q;
    while (q--){
        int t;
        cin >> t;
        cout << opt[t] << endl;
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Incorrect 3 ms 6612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 274 ms 39048 KB Output is correct
3 Correct 278 ms 50892 KB Output is correct
4 Correct 232 ms 39160 KB Output is correct
5 Correct 240 ms 38912 KB Output is correct
6 Correct 247 ms 41408 KB Output is correct
7 Correct 204 ms 38920 KB Output is correct
8 Correct 293 ms 53956 KB Output is correct
9 Correct 159 ms 37792 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 242 ms 39088 KB Output is correct
3 Correct 303 ms 56452 KB Output is correct
4 Correct 232 ms 44016 KB Output is correct
5 Correct 247 ms 45312 KB Output is correct
6 Correct 234 ms 47932 KB Output is correct
7 Correct 171 ms 45556 KB Output is correct
8 Correct 285 ms 58776 KB Output is correct
9 Correct 185 ms 43956 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Incorrect 3 ms 6612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 274 ms 39048 KB Output is correct
3 Correct 278 ms 50892 KB Output is correct
4 Correct 232 ms 39160 KB Output is correct
5 Correct 240 ms 38912 KB Output is correct
6 Correct 247 ms 41408 KB Output is correct
7 Correct 204 ms 38920 KB Output is correct
8 Correct 293 ms 53956 KB Output is correct
9 Correct 159 ms 37792 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 242 ms 39088 KB Output is correct
12 Correct 303 ms 56452 KB Output is correct
13 Correct 232 ms 44016 KB Output is correct
14 Correct 247 ms 45312 KB Output is correct
15 Correct 234 ms 47932 KB Output is correct
16 Correct 171 ms 45556 KB Output is correct
17 Correct 285 ms 58776 KB Output is correct
18 Correct 185 ms 43956 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Incorrect 242 ms 45488 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Incorrect 3 ms 6612 KB Output isn't correct
3 Halted 0 ms 0 KB -