oj.uz

답안 #708795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708795 2023-03-12T10:05:28 Z alvingogo Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 31384 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();
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 320 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 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 320 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 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 131 ms 636 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 126 ms 612 KB Output is correct
16 Correct 136 ms 632 KB Output is correct
17 Correct 132 ms 592 KB Output is correct
18 Correct 154 ms 596 KB Output is correct
19 Correct 144 ms 620 KB Output is correct
20 Correct 146 ms 636 KB Output is correct
21 Correct 148 ms 656 KB Output is correct
22 Correct 112 ms 660 KB Output is correct
23 Correct 178 ms 640 KB Output is correct
24 Correct 316 ms 632 KB Output is correct
25 Correct 30 ms 876 KB Output is correct
26 Correct 455 ms 628 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 320 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 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Execution timed out 2066 ms 27912 KB Time limit exceeded
14 Halted 0 ms 0 KB -