oj.uz

Submission #173703

# Submission time Handle Problem Language Result Execution time Memory
173703 2020-01-05T07:32:43 Z __d Factories (JOI14_factories) C++14
100 / 100
 5042 ms 205620 KB 
// 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

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16632 KB Output is correct
2 Correct 635 ms 35116 KB Output is correct
3 Correct 684 ms 35064 KB Output is correct
4 Correct 640 ms 35248 KB Output is correct
5 Correct 663 ms 35272 KB Output is correct
6 Correct 594 ms 35300 KB Output is correct
7 Correct 685 ms 34932 KB Output is correct
8 Correct 634 ms 35120 KB Output is correct
9 Correct 669 ms 35336 KB Output is correct
10 Correct 590 ms 35300 KB Output is correct
11 Correct 681 ms 35064 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16248 KB Output is correct
2 Correct 2252 ms 187336 KB Output is correct
3 Correct 3289 ms 186604 KB Output is correct
4 Correct 1132 ms 188000 KB Output is correct
5 Correct 4359 ms 198204 KB Output is correct
6 Correct 3559 ms 188904 KB Output is correct
7 Correct 1330 ms 68472 KB Output is correct
8 Correct 864 ms 69724 KB Output is correct
9 Correct 1325 ms 71068 KB Output is correct
10 Correct 1308 ms 70008 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16632 KB Output is correct
2 Correct 635 ms 35116 KB Output is correct
3 Correct 684 ms 35064 KB Output is correct
4 Correct 640 ms 35248 KB Output is correct
5 Correct 663 ms 35272 KB Output is correct
6 Correct 594 ms 35300 KB Output is correct
7 Correct 685 ms 34932 KB Output is correct
8 Correct 634 ms 35120 KB Output is correct
9 Correct 669 ms 35336 KB Output is correct
10 Correct 590 ms 35300 KB Output is correct
11 Correct 681 ms 35064 KB Output is correct
12 Correct 18 ms 16248 KB Output is correct
13 Correct 2252 ms 187336 KB Output is correct
14 Correct 3289 ms 186604 KB Output is correct
15 Correct 1132 ms 188000 KB Output is correct
16 Correct 4359 ms 198204 KB Output is correct
17 Correct 3559 ms 188904 KB Output is correct
18 Correct 1330 ms 68472 KB Output is correct
19 Correct 864 ms 69724 KB Output is correct
20 Correct 1325 ms 71068 KB Output is correct
21 Correct 1308 ms 70008 KB Output is correct
22 Correct 2951 ms 197404 KB Output is correct
23 Correct 2736 ms 198040 KB Output is correct
24 Correct 4116 ms 198248 KB Output is correct
25 Correct 4118 ms 199488 KB Output is correct
26 Correct 4100 ms 193844 KB Output is correct
27 Correct 5042 ms 205620 KB Output is correct
28 Correct 2212 ms 200836 KB Output is correct
29 Correct 4078 ms 194872 KB Output is correct
30 Correct 4188 ms 194848 KB Output is correct
31 Correct 4151 ms 195020 KB Output is correct
32 Correct 1513 ms 73108 KB Output is correct
33 Correct 1074 ms 72084 KB Output is correct
34 Correct 1169 ms 66840 KB Output is correct
35 Correct 1135 ms 66900 KB Output is correct
36 Correct 1311 ms 67064 KB Output is correct
37 Correct 1449 ms 67176 KB Output is correct