oj.uz

Submission #303643

# Submission time Handle Problem Language Result Execution time Memory
303643 2020-09-20T13:51:57 Z nickmet2004 Designated Cities (JOI19_designated_cities) C++11
13 / 100
 487 ms 32548 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;

typedef pair<int, int> ipair;
const int N = 2e5 + 5;
int n , q ,A , B , C , D;
ll dpD[N] , dpU[N] , cnt[N] ,was[N] , ans[N] ,dp[N];
struct Edge{
    int v , c, d;
    Edge(int v , int c , int d){this->v =v; this->c= c; this->d= d;}
};
int sumc , sum ;
vector<Edge> adj[N];
void dfsD(int u = 1, int p = 0){
    for(Edge X : adj[u]){
        int v = X.v;
        if(v==p) continue;
        dfsD(v , u);
        dpD[u] += dpD[v] + X.c;
    }
}
void dfsU(int u = 1 , int p = 0){
    for(Edge X : adj[u]){
        int v = X.v;
        if(v==p) continue;
        dpU[v] += dpU[u];
        dpU[v] += dpD[u] - (dpD[v] + X.c) + X.d;
        dfsU(v , u);
    }
}
ipair Find(int u){
    for(auto X : adj[u])if(!was[X.v]) return {X.v , X.d};
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; ++i){
        cin >> A >> B >> C >> D;
        adj[A].emplace_back(Edge(B , C , D)); adj[B].emplace_back(Edge(A , D , C));
        cnt[A]++; cnt[B]++;
    }
    dfsD();
    dfsU();
    //cout << ans[1] << " ans 1" << endl;
    ans[1] = 1e18;
    for(int i = 1; i <= n; ++i) ans[1] = min(ans[1] , dpD[i] + dpU[i]);
    set<pair<ll , int>> D;
    for(int i = 1; i <= n; ++i) if(cnt[i]==1) D.insert({Find(i).s , i});
    while(D.size() > 2){
        int u = D.begin()->s , w = D.begin()->f;
        D.erase(D.begin());
        was[u] = 1;
        int p = Find(u).f;
        --cnt[p];
        if(cnt[p] == 1){
            int x = Find(p).s;
            D.insert({w + x ,p});
        } else ans[D.size()] = ans[D.size() + 1] + w;
    }
    //for(int i = 1; i <= n; ++i) cout << dpD[i] << " "; cerr << endl;
    //for(int i = 1; i <= n; ++i) cout << dpU[i] << " "; cerr << endl;
    int q;
    cin >> q;
    while(q--){
        int k; cin >> k;
        cout << ans[k] << endl;
    }
return 0;
}

Compilation message

designated_cities.cpp: In function 'ipair Find(int)':
designated_cities.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 487 ms 25336 KB Output is correct
3 Correct 298 ms 28792 KB Output is correct
4 Correct 431 ms 25336 KB Output is correct
5 Correct 454 ms 25900 KB Output is correct
6 Correct 459 ms 27000 KB Output is correct
7 Correct 449 ms 28328 KB Output is correct
8 Correct 309 ms 31612 KB Output is correct
9 Correct 366 ms 32548 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Incorrect 10 ms 5248 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 487 ms 25336 KB Output is correct
3 Correct 298 ms 28792 KB Output is correct
4 Correct 431 ms 25336 KB Output is correct
5 Correct 454 ms 25900 KB Output is correct
6 Correct 459 ms 27000 KB Output is correct
7 Correct 449 ms 28328 KB Output is correct
8 Correct 309 ms 31612 KB Output is correct
9 Correct 366 ms 32548 KB Output is correct
10 Correct 3 ms 5120 KB Output is correct
11 Incorrect 458 ms 25336 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 487 ms 25336 KB Output is correct
14 Correct 298 ms 28792 KB Output is correct
15 Correct 431 ms 25336 KB Output is correct
16 Correct 454 ms 25900 KB Output is correct
17 Correct 459 ms 27000 KB Output is correct
18 Correct 449 ms 28328 KB Output is correct
19 Correct 309 ms 31612 KB Output is correct
20 Correct 366 ms 32548 KB Output is correct
21 Correct 3 ms 5120 KB Output is correct
22 Incorrect 458 ms 25336 KB Output isn't correct
23 Halted 0 ms 0 KB -