oj.uz

Submission #364524

# Submission time Handle Problem Language Result Execution time Memory
364524 2021-02-09T12:04:11 Z eric_xiao Factories (JOI14_factories) C++14
33 / 100
 8000 ms 262648 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);
    }
}
ll LCA(ll a,ll 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 70 ms 47980 KB Output is correct
2 Correct 2117 ms 57600 KB Output is correct
3 Correct 2125 ms 57196 KB Output is correct
4 Correct 2132 ms 60100 KB Output is correct
5 Correct 1679 ms 60052 KB Output is correct
6 Correct 1689 ms 60036 KB Output is correct
7 Correct 2109 ms 59760 KB Output is correct
8 Correct 2110 ms 59892 KB Output is correct
9 Correct 1679 ms 60068 KB Output is correct
10 Correct 1684 ms 59956 KB Output is correct
11 Correct 2112 ms 59628 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47596 KB Output is correct
2 Correct 2929 ms 241508 KB Output is correct
3 Correct 3668 ms 232684 KB Output is correct
4 Correct 2126 ms 242496 KB Output is correct
5 Correct 3537 ms 262648 KB Output is correct
6 Correct 3908 ms 244780 KB Output is correct
7 Correct 4022 ms 100332 KB Output is correct
8 Correct 2069 ms 101012 KB Output is correct
9 Correct 3210 ms 103200 KB Output is correct
10 Correct 3971 ms 101916 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 47980 KB Output is correct
2 Correct 2117 ms 57600 KB Output is correct
3 Correct 2125 ms 57196 KB Output is correct
4 Correct 2132 ms 60100 KB Output is correct
5 Correct 1679 ms 60052 KB Output is correct
6 Correct 1689 ms 60036 KB Output is correct
7 Correct 2109 ms 59760 KB Output is correct
8 Correct 2110 ms 59892 KB Output is correct
9 Correct 1679 ms 60068 KB Output is correct
10 Correct 1684 ms 59956 KB Output is correct
11 Correct 2112 ms 59628 KB Output is correct
12 Correct 35 ms 47596 KB Output is correct
13 Correct 2929 ms 241508 KB Output is correct
14 Correct 3668 ms 232684 KB Output is correct
15 Correct 2126 ms 242496 KB Output is correct
16 Correct 3537 ms 262648 KB Output is correct
17 Correct 3908 ms 244780 KB Output is correct
18 Correct 4022 ms 100332 KB Output is correct
19 Correct 2069 ms 101012 KB Output is correct
20 Correct 3210 ms 103200 KB Output is correct
21 Correct 3971 ms 101916 KB Output is correct
22 Execution timed out 8070 ms 242900 KB Time limit exceeded
23 Halted 0 ms 0 KB -