oj.uz

Submission #655159

# Submission time Handle Problem Language Result Execution time Memory
655159 2022-11-03T12:17:12 Z DJeniUp Designated Cities (JOI19_designated_cities) C++17
9 / 100
 680 ms 70888 KB 
#include "bits/stdc++.h"
//#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 100000000000000007
#define I 100000000000007
#define N 100007
#define endl '\n'
#define MOD 998244353

ll n,res,resx,d[2*N],res2,t[2*N],mn;

vector<pairll>v[2*N];

map<ll,ll>m[2*N];

priority_queue<ll>q,q1;

ll S(ll x,ll y){
    ll rs=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y){
            rs+=v[x][i].sc+S(v[x][i].fr,x);
        }
    }
    return rs;
}

void D(ll x,ll y,ll z){
    if(res>z){
        res=z;
        resx=x;
    }
    t[x]=z;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y){
            D(v[x][i].fr,x,z-v[x][i].sc+m[v[x][i].fr][x]);
        }
    }
    return ;
}

ll R(ll x,ll y){
    ll k=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y){
            ll r=R(v[x][i].fr,x)+v[x][i].sc;
            if(res2>t[x]-r-k){
                res2=min(t[x]-r-k,res2);
                mn=x;
            }
            if(k<r)swap(k,r);
        }
    }
    return k;
}

ll R1(ll x,ll y){
    ll k=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].fr!=y){
            ll r=R1(v[x][i].fr,x)+v[x][i].sc;
            if(k<r)swap(k,r);
            if(r!=0 && x!=mn)q.push(r);
            else if(r!=0)q1.push(r);
        }
    }
    return k;
}

int main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        ll x,y,z,z1;
        cin>>x>>y>>z>>z1;
        v[x].pb({y,z});
        v[y].pb({x,z1});
        m[x][y]=z;
        m[y][x]=z1;
    }
    res2=INF;
    res=INF;
    D(1,1,S(1,1));
    R(resx,0);
    //cout<<res<<endl;
    ll k=R1(mn,0);
    q1.push(k);
   // cout<<resx<<" "<<mn<<endl;
    //cout<<res<<" "<<res2<<endl;
    //cout<<k<<endl;
    res=t[mn];
    ll x=res;
    //cout<<"! "<<res<<" "<<resx<<endl;
    q1.push(0);
    res-=q1.top();
    //cout<<q1.top()<<endl;
    q1.pop();
    res-=q1.top();
    //cout<<q1.top()<<endl;
    q1.pop();
    d[2]=res;
    //cout<<"! "<<d[2]<<endl;
    while(q1.size()>0){
        q.push(q1.top());
        q1.pop();
    }
    for(int i=3;i<=n;i++){
        if(q.size()>0){
            res-=q.top();
            //cout<<i<<" "<<q.top()<<endl;
            q.pop();
        }
        d[i]=res;
    }
    d[1]=x;
    ll Q;
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>x;
        cout<<d[x]<<endl;
    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'll S(ll, ll)':
designated_cities.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void D(ll, ll, ll)':
designated_cities.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
designated_cities.cpp: In function 'll R(ll, ll)':
designated_cities.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
designated_cities.cpp: In function 'll R1(ll, ll)':
designated_cities.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 12 ms 14420 KB Output is correct
3 Correct 8 ms 14396 KB Output is correct
4 Correct 8 ms 14384 KB Output is correct
5 Incorrect 7 ms 14400 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 597 ms 53844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 638 ms 53880 KB Output is correct
3 Correct 651 ms 70888 KB Output is correct
4 Correct 608 ms 53856 KB Output is correct
5 Correct 604 ms 55144 KB Output is correct
6 Correct 638 ms 56564 KB Output is correct
7 Correct 601 ms 57320 KB Output is correct
8 Correct 680 ms 63888 KB Output is correct
9 Correct 586 ms 57476 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 12 ms 14420 KB Output is correct
3 Correct 8 ms 14396 KB Output is correct
4 Correct 8 ms 14384 KB Output is correct
5 Incorrect 7 ms 14400 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 597 ms 53844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 12 ms 14420 KB Output is correct
3 Correct 8 ms 14396 KB Output is correct
4 Correct 8 ms 14384 KB Output is correct
5 Incorrect 7 ms 14400 KB Output isn't correct
6 Halted 0 ms 0 KB -