oj.uz

Submission #362100

# Submission time Handle Problem Language Result Execution time Memory
362100 2021-02-01T18:41:10 Z denkendoemeer Factories (JOI14_factories) C++14
100 / 100
 6634 ms 344312 KB 
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool maxi(ll &a,ll b)
{
    if (a<b)
        return a=b,1;
    return 0;
}
bool mini(ll &a,ll b)
{
    if (a>b)
        return a=b,1;
    return 0;
}
struct ed
{
    int to,w;
};
vector<ed>e[500005];
struct grup
{
    int c;
    ll d;
};
vector<grup>g[500005];
int sum[500005],ok[500005];
ll ans,b1[500005],b2[500005];
int dfs(int nod,int t=-1)
{
    sum[nod]=1;
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            sum[nod]+=dfs(it.to,nod);
    return sum[nod];
}
int centr(int nod,int aux,int t=-1)
{
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            if (sum[it.to]*2>=aux)
                return centr(it.to,aux,nod);
    return nod;
}
int auxi;
void dfs2(int nod,int t=-1,ll dist=0)
{
    g[nod].push_back({auxi,dist});
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            dfs2(it.to,nod,dist+it.w);
}
void calc(int nod)
{
    int c=centr(nod,dfs(nod));
    auxi=c;
    dfs2(c);
    ok[c]=1;
    for(auto it:e[c])
        if (ok[it.to]==0)
            calc(it.to);
}
void Init(int n,int a[],int b[],int d[])
{
    int i;
    for(i=0;i<n-1;i++)
        e[a[i]].push_back({b[i],d[i]}),e[b[i]].push_back({a[i],d[i]});
    calc(0);
    memset(b1,0x3f,sizeof(b1));
    memset(b2,0x3f,sizeof(b2));
}
ll Query(int s,int x[],int t,int y[])
{
    ans=2e17;
    int i;
    for(i=0;i<s;i++)
        for(auto it:g[x[i]])
            mini(b2[it.c],it.d);
    for(i=0;i<t;i++)
        for(auto it:g[y[i]]){
            mini(b1[it.c],it.d);
            mini(ans,b1[it.c]+b2[it.c]);
        }
    for(i=0;i<s;i++)
        for(auto it:g[x[i]])
            b1[it.c]=b2[it.c]=2e17;
    for(i=0;i<t;i++)
        for(auto it:g[y[i]])
            b1[it.c]=b2[it.c]=2e17;
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32236 KB Output is correct
2 Correct 494 ms 50284 KB Output is correct
3 Correct 544 ms 50688 KB Output is correct
4 Correct 527 ms 50728 KB Output is correct
5 Correct 572 ms 51052 KB Output is correct
6 Correct 396 ms 49644 KB Output is correct
7 Correct 526 ms 50668 KB Output is correct
8 Correct 537 ms 50924 KB Output is correct
9 Correct 573 ms 50976 KB Output is correct
10 Correct 376 ms 49644 KB Output is correct
11 Correct 535 ms 50796 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31852 KB Output is correct
2 Correct 2943 ms 195116 KB Output is correct
3 Correct 4221 ms 264524 KB Output is correct
4 Correct 1197 ms 92508 KB Output is correct
5 Correct 5597 ms 337072 KB Output is correct
6 Correct 4605 ms 265068 KB Output is correct
7 Correct 1559 ms 83204 KB Output is correct
8 Correct 774 ms 61104 KB Output is correct
9 Correct 1648 ms 96752 KB Output is correct
10 Correct 1471 ms 84660 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32236 KB Output is correct
2 Correct 494 ms 50284 KB Output is correct
3 Correct 544 ms 50688 KB Output is correct
4 Correct 527 ms 50728 KB Output is correct
5 Correct 572 ms 51052 KB Output is correct
6 Correct 396 ms 49644 KB Output is correct
7 Correct 526 ms 50668 KB Output is correct
8 Correct 537 ms 50924 KB Output is correct
9 Correct 573 ms 50976 KB Output is correct
10 Correct 376 ms 49644 KB Output is correct
11 Correct 535 ms 50796 KB Output is correct
12 Correct 22 ms 31852 KB Output is correct
13 Correct 2943 ms 195116 KB Output is correct
14 Correct 4221 ms 264524 KB Output is correct
15 Correct 1197 ms 92508 KB Output is correct
16 Correct 5597 ms 337072 KB Output is correct
17 Correct 4605 ms 265068 KB Output is correct
18 Correct 1559 ms 83204 KB Output is correct
19 Correct 774 ms 61104 KB Output is correct
20 Correct 1648 ms 96752 KB Output is correct
21 Correct 1471 ms 84660 KB Output is correct
22 Correct 3896 ms 211056 KB Output is correct
23 Correct 3783 ms 206260 KB Output is correct
24 Correct 5550 ms 272772 KB Output is correct
25 Correct 5399 ms 276436 KB Output is correct
26 Correct 5203 ms 273532 KB Output is correct
27 Correct 6634 ms 344312 KB Output is correct
28 Correct 1934 ms 103228 KB Output is correct
29 Correct 5101 ms 272492 KB Output is correct
30 Correct 5127 ms 273016 KB Output is correct
31 Correct 5111 ms 272836 KB Output is correct
32 Correct 1966 ms 101100 KB Output is correct
33 Correct 968 ms 65552 KB Output is correct
34 Correct 1316 ms 80504 KB Output is correct
35 Correct 1314 ms 81132 KB Output is correct
36 Correct 1536 ms 86004 KB Output is correct
37 Correct 1582 ms 86380 KB Output is correct