oj.uz

Submission #674745

# Submission time Handle Problem Language Result Execution time Memory
674745 2022-12-26T06:16:39 Z lam Factories (JOI14_factories) C++14
100 / 100
 4357 ms 243204 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 23 ms 24276 KB Output is correct
2 Correct 308 ms 42100 KB Output is correct
3 Correct 306 ms 42404 KB Output is correct
4 Correct 311 ms 42308 KB Output is correct
5 Correct 318 ms 42664 KB Output is correct
6 Correct 243 ms 41728 KB Output is correct
7 Correct 302 ms 42308 KB Output is correct
8 Correct 299 ms 42336 KB Output is correct
9 Correct 331 ms 42580 KB Output is correct
10 Correct 212 ms 41732 KB Output is correct
11 Correct 307 ms 42288 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23964 KB Output is correct
2 Correct 2027 ms 138328 KB Output is correct
3 Correct 3206 ms 174588 KB Output is correct
4 Correct 745 ms 102104 KB Output is correct
5 Correct 3979 ms 243204 KB Output is correct
6 Correct 3241 ms 193716 KB Output is correct
7 Correct 1064 ms 70128 KB Output is correct
8 Correct 427 ms 58832 KB Output is correct
9 Correct 1032 ms 78364 KB Output is correct
10 Correct 959 ms 71292 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24276 KB Output is correct
2 Correct 308 ms 42100 KB Output is correct
3 Correct 306 ms 42404 KB Output is correct
4 Correct 311 ms 42308 KB Output is correct
5 Correct 318 ms 42664 KB Output is correct
6 Correct 243 ms 41728 KB Output is correct
7 Correct 302 ms 42308 KB Output is correct
8 Correct 299 ms 42336 KB Output is correct
9 Correct 331 ms 42580 KB Output is correct
10 Correct 212 ms 41732 KB Output is correct
11 Correct 307 ms 42288 KB Output is correct
12 Correct 15 ms 23964 KB Output is correct
13 Correct 2027 ms 138328 KB Output is correct
14 Correct 3206 ms 174588 KB Output is correct
15 Correct 745 ms 102104 KB Output is correct
16 Correct 3979 ms 243204 KB Output is correct
17 Correct 3241 ms 193716 KB Output is correct
18 Correct 1064 ms 70128 KB Output is correct
19 Correct 427 ms 58832 KB Output is correct
20 Correct 1032 ms 78364 KB Output is correct
21 Correct 959 ms 71292 KB Output is correct
22 Correct 2511 ms 143088 KB Output is correct
23 Correct 2446 ms 146700 KB Output is correct
24 Correct 3880 ms 181516 KB Output is correct
25 Correct 3731 ms 185152 KB Output is correct
26 Correct 3678 ms 181692 KB Output is correct
27 Correct 4357 ms 228572 KB Output is correct
28 Correct 929 ms 93424 KB Output is correct
29 Correct 3726 ms 181172 KB Output is correct
30 Correct 3753 ms 180764 KB Output is correct
31 Correct 3680 ms 181796 KB Output is correct
32 Correct 1054 ms 79104 KB Output is correct
33 Correct 368 ms 59088 KB Output is correct
34 Correct 693 ms 65040 KB Output is correct
35 Correct 714 ms 65496 KB Output is correct
36 Correct 948 ms 68284 KB Output is correct
37 Correct 914 ms 68404 KB Output is correct