oj.uz

Submission #708863

# Submission time Handle Problem Language Result Execution time Memory
708863 2023-03-12T13:48:28 Z alvingogo Designated Cities (JOI19_designated_cities) C++14
30 / 100
 261 ms 43468 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;
    pair<int,int> dp={0,-1},dp2={0,-1};
};
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];
}
pair<int,pair<int,int> > dfs4(int r,int f){
    pair<int,pair<int,int> > ret={0,{-1,-1}};
    auto c=v[r].dp,d=v[r].dp2;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            ret=max(ret,dfs4(h.fs,r));
            ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}});
            ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}});
            v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc});
            v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc});
        }
    }
    reverse(v[r].ch.begin(),v[r].ch.end());
    v[r].dp=c;
    v[r].dp2=d;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}});
            ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}});
            v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc});
            v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc});
        }
    }
    return ret;
}
void calc2(){
    for(int i=0;i<n;i++){
        if(v[i].ch.size()==1){
            v[i].dp.fs=v[i].sum;
            v[i].dp.sc=i;
            v[i].dp2.sc=i;
        }
    }
    auto h=dfs4(0,0);
    for(int i=0;i<n;i++){
        if(i==h.sc.fs || i==h.sc.sc){
            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);
            }
        }
    }
    assert(ans[2]==h.fs);
}
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:56: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]
   56 |         for(int i=1;i<g.size();i++){
      |                     ~^~~~~~~~~
designated_cities.cpp: In function 'void calc2()':
designated_cities.cpp:106: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]
  106 |             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 0 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 328 KB Output is correct
2 Correct 228 ms 35412 KB Output is correct
3 Correct 261 ms 43044 KB Output is correct
4 Correct 218 ms 34008 KB Output is correct
5 Correct 209 ms 35204 KB Output is correct
6 Correct 239 ms 36616 KB Output is correct
7 Correct 185 ms 34172 KB Output is correct
8 Correct 261 ms 43468 KB Output is correct
9 Correct 146 ms 33408 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 224 ms 32904 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 0 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 3 ms 724 KB Output is correct
14 Correct 3 ms 944 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 2 ms 692 KB Output is correct
21 Correct 3 ms 724 KB Output is correct
22 Correct 3 ms 724 KB Output is correct
23 Correct 2 ms 688 KB Output is correct
24 Correct 3 ms 724 KB Output is correct
25 Correct 3 ms 980 KB Output is correct
26 Correct 2 ms 700 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 228 ms 35412 KB Output is correct
3 Correct 261 ms 43044 KB Output is correct
4 Correct 218 ms 34008 KB Output is correct
5 Correct 209 ms 35204 KB Output is correct
6 Correct 239 ms 36616 KB Output is correct
7 Correct 185 ms 34172 KB Output is correct
8 Correct 261 ms 43468 KB Output is correct
9 Correct 146 ms 33408 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 224 ms 32904 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 228 ms 35412 KB Output is correct
14 Correct 261 ms 43044 KB Output is correct
15 Correct 218 ms 34008 KB Output is correct
16 Correct 209 ms 35204 KB Output is correct
17 Correct 239 ms 36616 KB Output is correct
18 Correct 185 ms 34172 KB Output is correct
19 Correct 261 ms 43468 KB Output is correct
20 Correct 146 ms 33408 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 224 ms 32904 KB Output isn't correct
23 Halted 0 ms 0 KB -