oj.uz

Submission #743547

# Submission time Handle Problem Language Result Execution time Memory
743547 2023-05-17T13:39:07 Z Valters07 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 121104 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:g[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 44 ms 24404 KB Output is correct
2 Correct 1280 ms 42284 KB Output is correct
3 Correct 1396 ms 42400 KB Output is correct
4 Correct 1302 ms 42488 KB Output is correct
5 Correct 1243 ms 42720 KB Output is correct
6 Correct 805 ms 42188 KB Output is correct
7 Correct 1370 ms 42292 KB Output is correct
8 Correct 1291 ms 42484 KB Output is correct
9 Correct 1198 ms 42764 KB Output is correct
10 Correct 802 ms 42340 KB Output is correct
11 Correct 1324 ms 42468 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24020 KB Output is correct
2 Execution timed out 8053 ms 121104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24404 KB Output is correct
2 Correct 1280 ms 42284 KB Output is correct
3 Correct 1396 ms 42400 KB Output is correct
4 Correct 1302 ms 42488 KB Output is correct
5 Correct 1243 ms 42720 KB Output is correct
6 Correct 805 ms 42188 KB Output is correct
7 Correct 1370 ms 42292 KB Output is correct
8 Correct 1291 ms 42484 KB Output is correct
9 Correct 1198 ms 42764 KB Output is correct
10 Correct 802 ms 42340 KB Output is correct
11 Correct 1324 ms 42468 KB Output is correct
12 Correct 17 ms 24020 KB Output is correct
13 Execution timed out 8053 ms 121104 KB Time limit exceeded
14 Halted 0 ms 0 KB -