제출 #173703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173703		__d	공장들 (JOI14_factories)	C++14	100 / 100	5042 ms	205620 KiB

factories

// assert subtask 3

#include <bits/stdc++.h>

#define minn(a,b) (a<=b?a:b)

typedef long long ll;
const int LV=20;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;

std::vector<std::pair<int,int> > g[500005];
int comproot[500005][LV];
ll compdist[500005][LV];
int nodelv[500005];

int sz[500005];

int depth=0;
void dfs(int u)
{
    sz[u]=1;
    for (auto &v:g[u]) {
        if (sz[v.first]) continue;
        dfs(v.first);
        sz[u]+=sz[v.first];
    }
}

int root;
void dfs2(int u)
{
    comproot[u][depth]=root;
    sz[u]=0;
    for (auto &v:g[u]) {
        if (!sz[v.first]) continue;
        compdist[v.first][depth]=compdist[u][depth]+v.second;
        dfs2(v.first);
    }
}

void centroid(int u)
{
    // base case
    if (g[u].empty()) {
        nodelv[u]=depth;
        comproot[u][depth]=u;
        compdist[u][depth]=0;
        return;
    }
    // get the component and centroid
    dfs(u);
    int minsz=sz[u]/2;
    bool go=1;
    while (go) {
        go=0;
        for (auto &v:g[u]) {
            if (minsz<sz[v.first] && sz[v.first]<sz[u]) {
                u=v.first;
                go=1;
                break;
            }
        }
    }
    nodelv[u]=depth;
    //printf("%d %d\n",u,depth);
    // get distances to centroid in this component
    root=u;
    dfs2(u);
    // do remaining components
    depth++;
    for (auto &v:g[u]) {
        if (v.first==u) continue;
        // remove edge and do centroid
        for (auto &v2:g[v.first]) {
            if (v2.first==u) {
                v2.first=v.first;
                break;
            }
        }
        centroid(v.first);
    }
    g[u].clear();
    depth--;
}

ll dists[500005];
int nn;
void Init(int n,int a[],int b[],int d[])
{
    nn=n;
    assert(2<=n && n<=500000);
    for (int i=0; i<n-1; i++) {
        assert(0<=a[i] && a[i]<=n-1);
        assert(0<=b[i] && b[i]<=n-1);
        assert(1<=d[i] && d[i]<=100000000);
        assert(a[i]!=b[i]);
        g[a[i]].push_back({b[i],d[i]});
        g[b[i]].push_back({a[i],d[i]});
    }
    centroid(0);
    memset(dists,0x3f,sizeof dists);
}

int clean0=0;
int clean1[500005];

int counter=0;
int scnt=0,tcnt=0;
ll Query(int s,int x[],int t,int y[])
{
    // assertions
    assert(1<=s && s<=nn-1);
    assert(1<=t && t<=nn-1);
    counter++;
    scnt+=s;
    tcnt+=t;
    assert(counter<=100000);
    assert(scnt<=1000000);
    assert(tcnt<=1000000);
    std::unordered_set<int> check;
    for (int i=0; i<s; i++) check.insert(x[i]);
    for (int i=0; i<t; i++) check.insert(y[i]);
    assert(check.size()==s+t);
    for (int i:check) assert(0<=i && i<=nn-1);
    if (s>t) {
        std::swap(s,t);
        std::swap(x,y);
    }
    // put x into dists
    for (int i=0; i<s; i++) {
        int u=x[i];
        for (int j=0; j<=nodelv[u]; j++) {
            //printf("%d %d %lld\n",x[i],comproot[x[i]][j],compdist[x[i]][j]);
            if (dists[comproot[u][j]]==INFLL) {
                dists[comproot[u][j]]=compdist[u][j];
                clean1[clean0++]=comproot[u][j];
            }
            else {
                dists[comproot[u][j]]=minn(dists[comproot[u][j]],compdist[u][j]);
            }
        }
    }
    // consider each y to get the answer
    long long ans=INFLL;
    for (int i=0; i<t; i++) {
        int u=y[i];
        for (int j=0; j<=nodelv[u]; j++) {
            ans=minn(ans,dists[comproot[u][j]]+compdist[u][j]);
        }
    }
    // clean up
    while (clean0) dists[clean1[--clean0]]=INFLL;
    return ans;
}

#ifdef NOT_DMOJ
int main()
{
    freopen("data.txt","r",stdin);
    int n,q;
    scanf("%d%d",&n,&q);
    int a[n-1],b[n-1],d[n-1];
    for (int i=0; i<n-1; i++) scanf("%d%d%d",a+i,b+i,d+i);
    Init(n,a,b,d);
    while (q--) {
        int s,t;
        scanf("%d%d",&s,&t);
        int x[s],y[t];
        for (int i=0; i<s; i++) scanf("%d",x+i);
        for (int i=0; i<t; i++) scanf("%d",y+i);
        printf("%lld\n",Query(s,x,t,y));
    }
}
#endif // NOT_DMOJ

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

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from factories.cpp:3:
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:124:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(check.size()==s+t);
            ~~~~~~~~~~~~^~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67