oj.uz

Submission #364528

# Submission time Handle Problem Language Result Execution time Memory
364528 2021-02-09T12:07:13 Z eric_xiao Factories (JOI14_factories) C++14
33 / 100
 8000 ms 244708 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
ll pre[500009],dep[500009],td[500009];
ll anc[500009][20],cnt = 0;
vector<ll> G[500009],d[500009];
vector<ll> G2[500009],d2[500009];
void DFS(ll u,ll p)
{
    anc[u][0] = p;
    cnt++;
    pre[u] = cnt;
    //cerr << u << "_" << td[u] << "_" << dep[u] << endl;
    for(int i = 1;i < 20;i++)
    {
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    for(int i = 0;i < G[u].size();i++)
    {
        int v = G[u][i];
        if(v == p) continue;
        dep[v] = dep[u] + d[u][i];
        td[v] = td[u] + 1;
        DFS(v,u);
    }
}
int LCA(int a,int b)
{
    if(a == 0 || b == 0) return 0LL;
    if(td[a] < td[b]) swap(a,b);
    int left = td[a] - td[b];
    for(int i = 0;i < 20;i++)
    {
        if((left>>i) & 1) a = anc[a][i];
    }
    if(a == b) return a;
    for(int i = 19;i >= 0;i--)
    {
        if(anc[a][i] != anc[b][i])
        {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}
const bool cmp(const ll &a,const ll & b)
{
    return pre[a] < pre[b];
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0;i < N-1;i++)
    {
        A[i]++;
        B[i]++;
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
        d[A[i]].push_back(D[i]);
        d[B[i]].push_back(D[i]);
    }
    td[1] = 1;
    DFS(1,0);
}
vector<ll> vs;
ll temp[500009];
ll stk[500009];
ll ans = 10000000000000000;
ll s,x[500009],t,y[500009];
ll ec = 0;
void add_edge(ll a,ll b)
{
    ll tp = abs(dep[a]-dep[b]);
    //cerr << a << "_" << b << "_" << tp << endl;
    G2[a].push_back(b);
    G2[b].push_back(a);
    d2[a].push_back(tp);
    d2[b].push_back(tp);
}
ll dis[500009];
set<ll> used;
void DKS()
{
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for(auto tt : used)
    {
        dis[tt] = 10000000000000000;
    }
    for(int i = 0;i < s;i++)
    {
        pq.push({0,x[i]});
    }
    while(!pq.empty())
    {
        ll u = pq.top().ss,tt = pq.top().ff;
        pq.pop();
        if(tt >= dis[u]) continue;
        dis[u] = tt;
        for(int i = 0;i < G2[u].size();i++)
        {
            ll v = G2[u][i];
            if(dis[v] < 10000000000000000) continue;
            pq.push({dis[u] + d2[u][i],v});
        }
    }
    for(int i = 0;i < t;i++)
    {
        ans = min(ans,dis[y[i]]);
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    vs.clear();
    s = S;
    used.clear();
    for(int i = 0;i < S;i++)
    {
        X[i]++;
        used.insert(X[i]);
        x[i] = X[i];
        G2[X[i]].clear();
        d2[X[i]].clear();
        temp[X[i]] = 1;
        vs.push_back(X[i]);
    }
    int fg = 0;
    t = T;
    for(int i = 0;i < T;i++)
    {
        Y[i]++;
        used.insert(Y[i]);
        y[i] = Y[i];
        G2[Y[i]].clear();
        d2[Y[i]].clear();
        vs.push_back(Y[i]);
        if(temp[Y[i]] == 1) fg = 1;
    }
    for(int i = 0;i < S;i++) temp[X[i]] = 0;
    if(fg == 1) return 0;
    sort(vs.begin(),vs.end(),cmp);
    stk[0] = 0;
    int sz = 1;
    ans = 10000000000000000;
    ec = 0;
    for(int i = 0;i < vs.size();i++)
    {
        ll u = vs[i];
        ll p = LCA(u,stk[sz-1]);
        //cerr << vs[i] << " p = " << p << endl;
        if(!used.count(p))
        {
            used.insert(p);
            G2[p].clear();
            d2[p].clear();
        }
        if(p == stk[sz-1]) stk[sz++] = u;
        else
        {
            while(sz > 1 && td[stk[sz-2]] >= td[p])
            {
                add_edge(stk[sz-1],stk[sz-2]);
                sz--;
            }
            if(stk[sz-1] != p)
            {
                add_edge(stk[sz-1],p);
                stk[sz-1] = p;
            }
            stk[sz++] = u;
        }
    }
    for (int i = 1; i < sz - 1; ++i) add_edge(stk[i], stk[i + 1]);
    DKS();
    return ans;
}

Compilation message

factories.cpp: In function 'void DFS(long long int, long long int)':
factories.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0;i < G[u].size();i++)
      |                   ~~^~~~~~~~~~~~~
factories.cpp: In function 'void DKS()':
factories.cpp:102:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = 0;i < G2[u].size();i++)
      |                       ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:147:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i = 0;i < vs.size();i++)
      |                   ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 47852 KB Output is correct
2 Correct 2037 ms 57816 KB Output is correct
3 Correct 2086 ms 57644 KB Output is correct
4 Correct 2009 ms 57912 KB Output is correct
5 Correct 1674 ms 57856 KB Output is correct
6 Correct 1596 ms 57760 KB Output is correct
7 Correct 2096 ms 57324 KB Output is correct
8 Correct 2054 ms 57716 KB Output is correct
9 Correct 1712 ms 57844 KB Output is correct
10 Correct 1588 ms 57628 KB Output is correct
11 Correct 2076 ms 57460 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47628 KB Output is correct
2 Correct 2822 ms 223468 KB Output is correct
3 Correct 3552 ms 224428 KB Output is correct
4 Correct 2025 ms 225084 KB Output is correct
5 Correct 3481 ms 244708 KB Output is correct
6 Correct 3787 ms 226660 KB Output is correct
7 Correct 3839 ms 92000 KB Output is correct
8 Correct 2044 ms 92592 KB Output is correct
9 Correct 3131 ms 94656 KB Output is correct
10 Correct 3803 ms 93496 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 47852 KB Output is correct
2 Correct 2037 ms 57816 KB Output is correct
3 Correct 2086 ms 57644 KB Output is correct
4 Correct 2009 ms 57912 KB Output is correct
5 Correct 1674 ms 57856 KB Output is correct
6 Correct 1596 ms 57760 KB Output is correct
7 Correct 2096 ms 57324 KB Output is correct
8 Correct 2054 ms 57716 KB Output is correct
9 Correct 1712 ms 57844 KB Output is correct
10 Correct 1588 ms 57628 KB Output is correct
11 Correct 2076 ms 57460 KB Output is correct
12 Correct 36 ms 47628 KB Output is correct
13 Correct 2822 ms 223468 KB Output is correct
14 Correct 3552 ms 224428 KB Output is correct
15 Correct 2025 ms 225084 KB Output is correct
16 Correct 3481 ms 244708 KB Output is correct
17 Correct 3787 ms 226660 KB Output is correct
18 Correct 3839 ms 92000 KB Output is correct
19 Correct 2044 ms 92592 KB Output is correct
20 Correct 3131 ms 94656 KB Output is correct
21 Correct 3803 ms 93496 KB Output is correct
22 Execution timed out 8060 ms 240808 KB Time limit exceeded
23 Halted 0 ms 0 KB -