oj.uz

Submission #364532

# Submission time Handle Problem Language Result Execution time Memory
364532 2021-02-09T12:14:29 Z eric_xiao Factories (JOI14_factories) C++14
33 / 100
 8000 ms 199408 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;
int pre[500009],td[500009];
ll dep[500009];
int anc[500009][20],cnt = 0;
vector<int> G[500009],d[500009];
vector<int> G2[500009];
vector<ll> d2[500009];
void DFS(int u,int 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 int &a,const int & 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;
int temp[500009];
int stk[500009];
ll ans = 10000000000000000;
int s,x[500009],t,y[500009];
void add_edge(int a,int 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<int> 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;
    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(int, int)':
factories.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0;i < G[u].size();i++)
      |                   ~~^~~~~~~~~~~~~
factories.cpp: In function 'void DKS()':
factories.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         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 71 ms 47724 KB Output is correct
2 Correct 2021 ms 57052 KB Output is correct
3 Correct 2127 ms 57068 KB Output is correct
4 Correct 2009 ms 57304 KB Output is correct
5 Correct 1693 ms 57428 KB Output is correct
6 Correct 1595 ms 57192 KB Output is correct
7 Correct 2060 ms 56864 KB Output is correct
8 Correct 2001 ms 57072 KB Output is correct
9 Correct 1713 ms 57536 KB Output is correct
10 Correct 1603 ms 57052 KB Output is correct
11 Correct 2063 ms 56880 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47596 KB Output is correct
2 Correct 2713 ms 173688 KB Output is correct
3 Correct 3417 ms 174544 KB Output is correct
4 Correct 1983 ms 176076 KB Output is correct
5 Correct 3357 ms 199408 KB Output is correct
6 Correct 3584 ms 176584 KB Output is correct
7 Correct 3642 ms 82320 KB Output is correct
8 Correct 1925 ms 83020 KB Output is correct
9 Correct 2979 ms 85672 KB Output is correct
10 Correct 3547 ms 83040 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 47724 KB Output is correct
2 Correct 2021 ms 57052 KB Output is correct
3 Correct 2127 ms 57068 KB Output is correct
4 Correct 2009 ms 57304 KB Output is correct
5 Correct 1693 ms 57428 KB Output is correct
6 Correct 1595 ms 57192 KB Output is correct
7 Correct 2060 ms 56864 KB Output is correct
8 Correct 2001 ms 57072 KB Output is correct
9 Correct 1713 ms 57536 KB Output is correct
10 Correct 1603 ms 57052 KB Output is correct
11 Correct 2063 ms 56880 KB Output is correct
12 Correct 36 ms 47596 KB Output is correct
13 Correct 2713 ms 173688 KB Output is correct
14 Correct 3417 ms 174544 KB Output is correct
15 Correct 1983 ms 176076 KB Output is correct
16 Correct 3357 ms 199408 KB Output is correct
17 Correct 3584 ms 176584 KB Output is correct
18 Correct 3642 ms 82320 KB Output is correct
19 Correct 1925 ms 83020 KB Output is correct
20 Correct 2979 ms 85672 KB Output is correct
21 Correct 3547 ms 83040 KB Output is correct
22 Execution timed out 8025 ms 188820 KB Time limit exceeded
23 Halted 0 ms 0 KB -