oj.uz

Submission #674746

# Submission time Handle Problem Language Result Execution time Memory
674746 2022-12-26T06:19:18 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4232 ms 224620 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,long long> ii;
#define ff first
#define ss second
const int maxn = 5e5 + 10;
int n,q;
vector <ii> adj[maxn];
int s[maxn],par[maxn];
long long d[maxn];
bool dau[maxn];
vector <long long> depth[maxn];

int get_sz(int x, int p)
{
    s[x]=1;
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff])
            s[x]+=get_sz(i.ff,x);
    return s[x];
}

int find_centroid(int x, int p, int sz)
{
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]&&s[i.ff]*2>sz) return find_centroid(i.ff,x,sz);
    return x;
}

void dfs(int x, int p, long long dep)
{
    depth[x].push_back(dep);
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]) dfs(i.ff,x,1LL*dep+i.ss);
}

void decompose(int x, int p)
{
    x=find_centroid(x,x,get_sz(x,x));
    dau[x]=1;
    depth[x].push_back(0);
    par[x]=p;
    d[x]=1e18;
    for (ii i:adj[x])
        if (!dau[i.ff])
        {
            dfs(i.ff,x,1LL*i.ss);
            decompose(i.ff,x);
        }
}

void color(int x)
{
    int p=x;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        long long j=depth[x][i];
        d[p]=min(d[p],j);
        p=par[p];
    }
}
long long qry(int x)
{
    int p=x;
    long long ans=1e18;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        long long j=depth[x][i];
        if (d[p]!=1e18) ans=min(ans,d[p]+j);
        p=par[p];
    }
    return ans;
}
void xoa(int x)
{
    int p=x;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        long long j=depth[x][i];
        d[p]=1e18;
        p=par[p];
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=1; i<=n; i++)
    {
        adj[i].clear();
        dau[i]=0;
    }
    for (int i=0; i<n-1; i++)
    {
        int u=A[i]; int v=B[i]; long long w=D[i];
        u++; v++;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    decompose(1,-1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; i++) color(++X[i]);
    long long ans = 1e18;
    for (int i=0; i<T; i++) ans=min(ans,qry(++Y[i]));
    for (int i=0; i<S; i++) xoa(X[i]);
  return ans;
}

Compilation message

factories.cpp: In function 'void xoa(int)':
factories.cpp:79:19: warning: unused variable 'j' [-Wunused-variable]
   79 |         long long j=depth[x][i];
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24276 KB Output is correct
2 Correct 279 ms 33140 KB Output is correct
3 Correct 314 ms 33284 KB Output is correct
4 Correct 300 ms 33572 KB Output is correct
5 Correct 337 ms 33896 KB Output is correct
6 Correct 215 ms 33168 KB Output is correct
7 Correct 296 ms 33596 KB Output is correct
8 Correct 320 ms 33668 KB Output is correct
9 Correct 355 ms 33904 KB Output is correct
10 Correct 228 ms 33084 KB Output is correct
11 Correct 294 ms 33576 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24032 KB Output is correct
2 Correct 2070 ms 137608 KB Output is correct
3 Correct 3066 ms 174560 KB Output is correct
4 Correct 734 ms 83828 KB Output is correct
5 Correct 3819 ms 224620 KB Output is correct
6 Correct 3234 ms 175020 KB Output is correct
7 Correct 973 ms 56604 KB Output is correct
8 Correct 370 ms 45292 KB Output is correct
9 Correct 1091 ms 64616 KB Output is correct
10 Correct 992 ms 57924 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24276 KB Output is correct
2 Correct 279 ms 33140 KB Output is correct
3 Correct 314 ms 33284 KB Output is correct
4 Correct 300 ms 33572 KB Output is correct
5 Correct 337 ms 33896 KB Output is correct
6 Correct 215 ms 33168 KB Output is correct
7 Correct 296 ms 33596 KB Output is correct
8 Correct 320 ms 33668 KB Output is correct
9 Correct 355 ms 33904 KB Output is correct
10 Correct 228 ms 33084 KB Output is correct
11 Correct 294 ms 33576 KB Output is correct
12 Correct 14 ms 24032 KB Output is correct
13 Correct 2070 ms 137608 KB Output is correct
14 Correct 3066 ms 174560 KB Output is correct
15 Correct 734 ms 83828 KB Output is correct
16 Correct 3819 ms 224620 KB Output is correct
17 Correct 3234 ms 175020 KB Output is correct
18 Correct 973 ms 56604 KB Output is correct
19 Correct 370 ms 45292 KB Output is correct
20 Correct 1091 ms 64616 KB Output is correct
21 Correct 992 ms 57924 KB Output is correct
22 Correct 2454 ms 138048 KB Output is correct
23 Correct 2483 ms 141588 KB Output is correct
24 Correct 3698 ms 176132 KB Output is correct
25 Correct 3643 ms 179904 KB Output is correct
26 Correct 3562 ms 176860 KB Output is correct
27 Correct 4232 ms 223172 KB Output is correct
28 Correct 925 ms 88148 KB Output is correct
29 Correct 3564 ms 176232 KB Output is correct
30 Correct 3538 ms 175320 KB Output is correct
31 Correct 3556 ms 176112 KB Output is correct
32 Correct 1095 ms 65568 KB Output is correct
33 Correct 353 ms 45432 KB Output is correct
34 Correct 744 ms 51904 KB Output is correct
35 Correct 693 ms 52172 KB Output is correct
36 Correct 911 ms 55000 KB Output is correct
37 Correct 910 ms 55120 KB Output is correct