oj.uz

답안 #592280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592280 2022-07-08T20:53:26 Z Lobo Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 35892 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, q, comp[maxn], mark[maxn], ans[maxn], pai[maxn];
pair<int,int> dp[maxn];
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<int> vert, g[maxn];

int dfsdeep(int u, int ant, int val) {
    vert.pb(u);
    pai[u] = ant;
    dp[u] = mp(val,u);
    int up = 0;
    for(auto id : g[u]) {
        int v = u^edg[id].fr.fr^edg[id].fr.sc;
        if(v == ant) continue;
        int w;
        if(edg[id].fr.fr == u) w = edg[id].sc.fr;
        else w = edg[id].sc.sc;
        if(ant == 0) 
            comp[v] = v;
        else
            comp[v] = comp[u];
        up+= edg[id].sc.fr+edg[id].sc.sc-w;
        up+= dfsdeep(v,u,w);
        dp[u] = max(dp[u],mp(dp[v].fr+val,dp[v].sc));
    }
    return up;
}

void sol(int rt) {
    vert.clear();
    int up = dfsdeep(rt,0,0);
    vector<pair<int,int>> deeps;
    //pego eu mesmo e os melhores dos outros
    for(auto v : vert) {
        mark[v] = 0;
        deeps.pb(mp(dp[v].fr,v));
    }
    sort(all(deeps),greater<pair<int,int>>());

    int qtdc = 1;
    int ans1 = up;
    ans[1] = max(ans[1],ans1);
    // for(auto X : deeps) {
    //     int v = X.sc;
    //     if(mark[v]) continue;
    //     ans1+= dp[v].fr;
    //     qtdc++;
    //     ans[qtdc] = max(ans[qtdc],ans1);
    //     v = dp[v].sc;
    //     // cout << v << " " << X.fr << endl;

    //     while(v != 0 && mark[v] == 0) {
    //         mark[v] = 1;
    //         v = pai[v];
    //     }
    // }

    //obriga a escolher de subs diferentes
    ans1 = up;
    qtdc = 2;
    for(auto v : vert) {
        mark[v] = 0;
    }
    int v1 = dp[rt].sc;
    ans1+= dp[rt].fr;
    int comp1 = comp[v1];
    while(v1 != 0 && mark[v1] == 0) {
        mark[v1] = 1;
        v1 = pai[v1];
    }

    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v] || comp[dp[v].sc] == comp1) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
        break;
    }
    
    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v]) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
    }

}

void solve() {
    cin >> n;
    for(int i = 0; i < n-1; i++) {
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        g[u].pb(i);
        g[v].pb(i);
        ans[0]+= w1+w2;
        edg.pb(mp(mp(u,v),mp(w1,w2)));
    }

    for(int i = 1; i <= n; i++) {
        sol(i);
    }
    for(int i = 2; i <= n; i++) {
        ans[i] = max(ans[i],ans[i-1]);
    }

    cin >> q;
    while(q--) {
        int x; cin >> x;
        cout << ans[0]-ans[x] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2069 ms 35892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2069 ms 35892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -