oj.uz

Submission #743551

# Submission time Handle Problem Language Result Execution time Memory
743551 2023-05-17T13:42:35 Z Valters07 Factories (JOI14_factories) C++14
100 / 100
 3589 ms 174864 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define en cin.close();return 0;
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 5e5+5;
const int LOG = log2(N)+2;
vector<pair<int,int> > g[N];
vector<pair<int,ll> > g2[N];
int par[N][LOG];
int tin[N], tout[N], tt;
int col[N];
ll dist[N], mindist;
void dfs(int u, int p)
{
    tin[u]=++tt;
    par[u][0]=p;
    for(int i = 1;i<LOG;i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:g[u])
        if(v.fi!=p)
            dist[v.fi]=dist[u]+v.se,
            dfs(v.fi,u);
    tout[u]=tt;
}
bool isanc(int u, int v)
{
    return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
int lca(int u, int v)
{
    if(isanc(u,v))
        return u;
    if(isanc(v,u))
        return v;
    for(int i = LOG-1;i>=0;i--)
        if(!isanc(par[u][i],v))
            u=par[u][i];
    return par[u][0];
}
void Init(int n, int a[], int b[], int d[])
{
    for(int i = 0;i<n-1;i++)
        g[a[i]].pb({b[i],d[i]}),
        g[b[i]].pb({a[i],d[i]});
    dfs(0,0);
}
void con(int u, int v)
{
    if(u==v)
        return;
    ll d = abs(dist[u]-dist[v]);
    g2[u].pb({v,d});
    g2[v].pb({u,d});
}
int createvt(vector<int> &nodes)
{
    sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);});
    for(int i = (int)(nodes.size())-2;i>=0;i--)
        nodes.pb(lca(nodes[i],nodes[i+1]));
    sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);});
    vector<int> ve;
    ve.pb(nodes[0]);
    for(int i = 1;i<nodes.size();i++)
    {
        while(!isanc(ve.back(),nodes[i]))
            con(ve.back(),ve[ve.size()-2]),
            ve.pop_back();
        ve.pb(nodes[i]);
    }
    while(ve.size()>1)
        con(ve.back(),ve[ve.size()-2]),
        ve.pop_back();
    return ve[0];
}
pair<ll,ll> dfs2(int u, int p)
{
    ll min1 = 1e18, min2 = 1e18;
    if(col[u]==1)
        min1=0;
    else if(col[u]==2)
        min2=0;
    for(auto v:g2[u])
    {
        if(v.fi!=p)
        {
            pair<ll,ll> t = dfs2(v.fi,u);
            min1=min(min1,t.fi+v.se);
            min2=min(min2,t.se+v.se);
        }
    }
    mindist=min(mindist,min1+min2);
    return {min1,min2};
}
long long Query(int n, int x[], int m, int y[])
{
    vector<int> nodes;
    for(int i = 0;i<n;i++)
        nodes.pb(x[i]),
        col[x[i]]=1;
    for(int i = 0;i<m;i++)
        nodes.pb(y[i]),
        col[y[i]]=2;
    int r = createvt(nodes);
    mindist = 1e18;
    dfs2(r,r);
    for(auto x:nodes)
        g2[x].clear(),
        col[x]=0;
    return mindist;
}

Compilation message

factories.cpp: In function 'int createvt(std::vector<int>&)':
factories.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1;i<nodes.size();i++)
      |                   ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24404 KB Output is correct
2 Correct 902 ms 34220 KB Output is correct
3 Correct 815 ms 34164 KB Output is correct
4 Correct 898 ms 34276 KB Output is correct
5 Correct 647 ms 34460 KB Output is correct
6 Correct 746 ms 34160 KB Output is correct
7 Correct 943 ms 34200 KB Output is correct
8 Correct 837 ms 34324 KB Output is correct
9 Correct 667 ms 34584 KB Output is correct
10 Correct 695 ms 34168 KB Output is correct
11 Correct 873 ms 34308 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 1501 ms 118340 KB Output is correct
3 Correct 2187 ms 138936 KB Output is correct
4 Correct 1214 ms 137040 KB Output is correct
5 Correct 1552 ms 167304 KB Output is correct
6 Correct 2209 ms 141472 KB Output is correct
7 Correct 1682 ms 65900 KB Output is correct
8 Correct 1059 ms 66060 KB Output is correct
9 Correct 827 ms 70616 KB Output is correct
10 Correct 1695 ms 67408 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24404 KB Output is correct
2 Correct 902 ms 34220 KB Output is correct
3 Correct 815 ms 34164 KB Output is correct
4 Correct 898 ms 34276 KB Output is correct
5 Correct 647 ms 34460 KB Output is correct
6 Correct 746 ms 34160 KB Output is correct
7 Correct 943 ms 34200 KB Output is correct
8 Correct 837 ms 34324 KB Output is correct
9 Correct 667 ms 34584 KB Output is correct
10 Correct 695 ms 34168 KB Output is correct
11 Correct 873 ms 34308 KB Output is correct
12 Correct 19 ms 24064 KB Output is correct
13 Correct 1501 ms 118340 KB Output is correct
14 Correct 2187 ms 138936 KB Output is correct
15 Correct 1214 ms 137040 KB Output is correct
16 Correct 1552 ms 167304 KB Output is correct
17 Correct 2209 ms 141472 KB Output is correct
18 Correct 1682 ms 65900 KB Output is correct
19 Correct 1059 ms 66060 KB Output is correct
20 Correct 827 ms 70616 KB Output is correct
21 Correct 1695 ms 67408 KB Output is correct
22 Correct 2656 ms 153264 KB Output is correct
23 Correct 2441 ms 153752 KB Output is correct
24 Correct 3452 ms 156656 KB Output is correct
25 Correct 3589 ms 159672 KB Output is correct
26 Correct 3363 ms 151052 KB Output is correct
27 Correct 2632 ms 174864 KB Output is correct
28 Correct 1875 ms 151512 KB Output is correct
29 Correct 3317 ms 149912 KB Output is correct
30 Correct 3341 ms 149424 KB Output is correct
31 Correct 3178 ms 149840 KB Output is correct
32 Correct 1188 ms 72764 KB Output is correct
33 Correct 1134 ms 69644 KB Output is correct
34 Correct 1542 ms 65048 KB Output is correct
35 Correct 1559 ms 64904 KB Output is correct
36 Correct 1707 ms 65416 KB Output is correct
37 Correct 1675 ms 65388 KB Output is correct