제출 #743547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743547		Valters07	공장들 (JOI14_factories)	C++14	15 / 100	8053 ms	121104 KiB

factories

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67