oj.uz

Submission #303573

# Submission time Handle Problem Language Result Execution time Memory
303573 2020-09-20T12:54:21 Z nickmet2004 Designated Cities (JOI19_designated_cities) C++11
13 / 100
 480 ms 32416 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];
struct Edge{
    int v , c, d;
    Edge(int v , int c , int d){this->v =v; this->c= c; this->d= d;}
};
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:35:1: warning: control reaches end of non-void function [-Wreturn-type]
   35 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5024 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 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 4992 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 468 ms 25464 KB Output is correct
3 Correct 308 ms 28792 KB Output is correct
4 Correct 428 ms 25336 KB Output is correct
5 Correct 459 ms 26032 KB Output is correct
6 Correct 462 ms 27000 KB Output is correct
7 Correct 451 ms 28328 KB Output is correct
8 Correct 317 ms 31612 KB Output is correct
9 Correct 372 ms 32416 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 480 ms 25244 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 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5024 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 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 4992 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 468 ms 25464 KB Output is correct
3 Correct 308 ms 28792 KB Output is correct
4 Correct 428 ms 25336 KB Output is correct
5 Correct 459 ms 26032 KB Output is correct
6 Correct 462 ms 27000 KB Output is correct
7 Correct 451 ms 28328 KB Output is correct
8 Correct 317 ms 31612 KB Output is correct
9 Correct 372 ms 32416 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Incorrect 480 ms 25244 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 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5024 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 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 4992 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 468 ms 25464 KB Output is correct
14 Correct 308 ms 28792 KB Output is correct
15 Correct 428 ms 25336 KB Output is correct
16 Correct 459 ms 26032 KB Output is correct
17 Correct 462 ms 27000 KB Output is correct
18 Correct 451 ms 28328 KB Output is correct
19 Correct 317 ms 31612 KB Output is correct
20 Correct 372 ms 32416 KB Output is correct
21 Correct 4 ms 5120 KB Output is correct
22 Incorrect 480 ms 25244 KB Output isn't correct
23 Halted 0 ms 0 KB -