oj.uz

Submission #708797

# Submission time Handle Problem Language Result Execution time Memory
708797 2023-03-12T10:06:18 Z alvingogo Designated Cities (JOI19_designated_cities) C++14
30 / 100
 430 ms 34068 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct no{
    vector<pair<int,pair<int,int> > > ch;
    int sum=0;
    int sum2=0;
};
int n;
int zz=0;
vector<no> v;
vector<int> ans;
void dfs(int r,int f){
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs(h.fs,r);
            v[r].sum+=v[h.fs].sum+h.sc.sc;
        }
    }
}
void dfs2(int r,int f,int z=0){
    v[r].sum+=z;
    ans[1]=max(ans[1],v[r].sum);
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs2(h.fs,r,h.sc.fs+v[r].sum-v[h.fs].sum-h.sc.sc);
        }
    }
}
void calc1(){
    dfs(0,0);
    ans[1]=max(ans[1],v[0].sum);
    dfs2(0,0);
}
vector<int> t;
void dfs3(int r,int f){
    vector<int> g;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs3(h.fs,r);
            g.push_back(v[h.fs].sum2+h.sc.fs);
        }
    }
    sort(g.begin(),g.end(),greater<int>());
    if(!g.size()){
        return;
    }
    if(g.size()>1){
        for(int i=1;i<g.size();i++){
            t.push_back(g[i]);
        }
    }
    v[r].sum2=g[0];
}
void calc2(){
    for(int i=0;i<n;i++){
        if(v[i].ch.size()==1){
            for(int j=0;j<n;j++){
                v[j].sum2=0;
            }
            t.clear();
            dfs3(i,i);
            t.push_back(v[i].sum2);
            sort(t.begin(),t.end(),greater<int>());
            int nw=v[i].sum;
            while(t.size()<=n){
                t.push_back(0);
            }
            for(int j=2;j<=n;j++){
                nw+=t[j-2];
                ans[j]=max(ans[j],nw);
            }
        }
    }
}
signed main(){
    AquA;
    cin >> n;
    v.resize(n);
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        int c,d;
        cin >> c >> d;
        zz+=c+d;
        v[a].ch.push_back({b,{c,d}});
        v[b].ch.push_back({a,{d,c}});
    }
    ans.resize(n+1);
    calc1();
    if(n<=2000){
        calc2();
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int a;
        cin >> a;
        cout << zz-ans[a] << "\n";
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void dfs3(long long int, long long int)':
designated_cities.cpp:55:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=1;i<g.size();i++){
      |                     ~^~~~~~~~~
designated_cities.cpp: In function 'void calc2()':
designated_cities.cpp:72:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   72 |             while(t.size()<=n){
      |                   ~~~~~~~~^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 250 ms 23276 KB Output is correct
3 Correct 327 ms 33680 KB Output is correct
4 Correct 230 ms 26220 KB Output is correct
5 Correct 208 ms 25896 KB Output is correct
6 Correct 224 ms 27408 KB Output is correct
7 Correct 172 ms 24836 KB Output is correct
8 Correct 244 ms 34068 KB Output is correct
9 Correct 134 ms 23908 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 142 ms 632 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 125 ms 624 KB Output is correct
16 Correct 133 ms 596 KB Output is correct
17 Correct 135 ms 716 KB Output is correct
18 Correct 133 ms 632 KB Output is correct
19 Correct 133 ms 636 KB Output is correct
20 Correct 142 ms 636 KB Output is correct
21 Correct 136 ms 664 KB Output is correct
22 Correct 111 ms 640 KB Output is correct
23 Correct 160 ms 620 KB Output is correct
24 Correct 304 ms 632 KB Output is correct
25 Correct 29 ms 852 KB Output is correct
26 Correct 430 ms 628 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 250 ms 23276 KB Output is correct
3 Correct 327 ms 33680 KB Output is correct
4 Correct 230 ms 26220 KB Output is correct
5 Correct 208 ms 25896 KB Output is correct
6 Correct 224 ms 27408 KB Output is correct
7 Correct 172 ms 24836 KB Output is correct
8 Correct 244 ms 34068 KB Output is correct
9 Correct 134 ms 23908 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 218 ms 22896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 250 ms 23276 KB Output is correct
14 Correct 327 ms 33680 KB Output is correct
15 Correct 230 ms 26220 KB Output is correct
16 Correct 208 ms 25896 KB Output is correct
17 Correct 224 ms 27408 KB Output is correct
18 Correct 172 ms 24836 KB Output is correct
19 Correct 244 ms 34068 KB Output is correct
20 Correct 134 ms 23908 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Incorrect 218 ms 22896 KB Output isn't correct
23 Halted 0 ms 0 KB -