oj.uz

Submission #958164

# Submission time Handle Problem Language Result Execution time Memory
958164 2024-04-05T05:02:10 Z irmuun Factories (JOI14_factories) C++17
100 / 100
 2597 ms 122772 KB 
#include<bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const int N=5e5+5;
vector<ll>dist(N);
vector<int>sz(N),heavy(N,-1),head(N),par(N);
vector<pair<int,int>>adj[N];

void dfs(int x){
    sz[x]=1;
    int mx=0;
    for(auto [y,w]:adj[x]){
        if(y!=par[x]){
            dist[y]=dist[x]+w;
            par[y]=x;
            dfs(y);
            sz[x]+=sz[y];
            if(sz[y]>mx){
                mx=sz[y];
                heavy[x]=y;
            }
        }
    }
}
void HLD(int x,int h){
    head[x]=h;
    if(heavy[x]>-1){
        HLD(heavy[x],h);
    }
    for(auto [y,w]:adj[x]){
        if(y!=par[x]&&y!=heavy[x]){
            HLD(y,y);
        }
    }
}
 
void Init(int n,int a[],int b[],int d[]){
    for(int i=0;i<n-1;i++){
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
    par[0]=-1;
    dfs(0);
    HLD(0,0);
}
 
ll Query(int s,int x[],int t,int y[]){
    vector<array<ll,4>>v;
    for(int i=0;i<s;i++){
        int j=x[i];
        v.pb({head[j],-dist[j],x[i],0});
        j=head[j];
        while(j>0){
            j=par[j];
            v.pb({head[j],-dist[j],x[i],0});
            j=head[j];
        }
    }
    for(int i=0;i<t;i++){
        int j=y[i];
        v.pb({head[j],-dist[j],y[i],1});
        j=head[j];
        while(j>0){
            j=par[j];
            v.pb({head[j],-dist[j],y[i],1});
            j=head[j];
        }
    }
    sort(all(v));
    vector<array<ll,3>>cur;
    ll ans=1e18;
    for(int i=0;i<v.size();i++){
        cur.pb({-v[i][1],v[i][2],v[i][3]});
        if(i==(int)v.size()-1||v[i][0]!=v[i+1][0]){
            ll mn0=1e18,mn1=1e18;
            for(int j=0;j<cur.size();j++){
                if(cur[j][2]==0){
                    mn0=min(mn0,dist[cur[j][1]]);
                    ans=min(ans,dist[cur[j][1]]+mn1-2*cur[j][0]);
                }
                else{
                    mn1=min(mn1,dist[cur[j][1]]);
                    ans=min(ans,dist[cur[j][1]]+mn0-2*cur[j][0]);
                }
            }
            cur.clear();
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
factories.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int j=0;j<cur.size();j++){
      |                         ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41300 KB Output is correct
2 Correct 1057 ms 56184 KB Output is correct
3 Correct 703 ms 55120 KB Output is correct
4 Correct 817 ms 55756 KB Output is correct
5 Correct 385 ms 55424 KB Output is correct
6 Correct 583 ms 55324 KB Output is correct
7 Correct 678 ms 54960 KB Output is correct
8 Correct 698 ms 55708 KB Output is correct
9 Correct 391 ms 55424 KB Output is correct
10 Correct 556 ms 55352 KB Output is correct
11 Correct 667 ms 55148 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 41048 KB Output is correct
2 Correct 1063 ms 84580 KB Output is correct
3 Correct 735 ms 87620 KB Output is correct
4 Correct 485 ms 84964 KB Output is correct
5 Correct 669 ms 115380 KB Output is correct
6 Correct 718 ms 88144 KB Output is correct
7 Correct 608 ms 63848 KB Output is correct
8 Correct 465 ms 63968 KB Output is correct
9 Correct 438 ms 67412 KB Output is correct
10 Correct 602 ms 64572 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41300 KB Output is correct
2 Correct 1057 ms 56184 KB Output is correct
3 Correct 703 ms 55120 KB Output is correct
4 Correct 817 ms 55756 KB Output is correct
5 Correct 385 ms 55424 KB Output is correct
6 Correct 583 ms 55324 KB Output is correct
7 Correct 678 ms 54960 KB Output is correct
8 Correct 698 ms 55708 KB Output is correct
9 Correct 391 ms 55424 KB Output is correct
10 Correct 556 ms 55352 KB Output is correct
11 Correct 667 ms 55148 KB Output is correct
12 Correct 10 ms 41048 KB Output is correct
13 Correct 1063 ms 84580 KB Output is correct
14 Correct 735 ms 87620 KB Output is correct
15 Correct 485 ms 84964 KB Output is correct
16 Correct 669 ms 115380 KB Output is correct
17 Correct 718 ms 88144 KB Output is correct
18 Correct 608 ms 63848 KB Output is correct
19 Correct 465 ms 63968 KB Output is correct
20 Correct 438 ms 67412 KB Output is correct
21 Correct 602 ms 64572 KB Output is correct
22 Correct 2597 ms 120284 KB Output is correct
23 Correct 2069 ms 120988 KB Output is correct
24 Correct 1615 ms 108392 KB Output is correct
25 Correct 1424 ms 108580 KB Output is correct
26 Correct 1328 ms 93248 KB Output is correct
27 Correct 1028 ms 122772 KB Output is correct
28 Correct 948 ms 105036 KB Output is correct
29 Correct 1187 ms 91800 KB Output is correct
30 Correct 1250 ms 91012 KB Output is correct
31 Correct 1155 ms 91852 KB Output is correct
32 Correct 602 ms 76796 KB Output is correct
33 Correct 734 ms 78228 KB Output is correct
34 Correct 1574 ms 61928 KB Output is correct
35 Correct 1383 ms 63288 KB Output is correct
36 Correct 808 ms 63328 KB Output is correct
37 Correct 782 ms 63292 KB Output is correct