oj.uz

Submission #364536

# Submission time Handle Problem Language Result Execution time Memory
364536 2021-02-09T12:26:04 Z eric_xiao Factories (JOI14_factories) C++14
33 / 100
 8000 ms 211304 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 iss[500009],ist[500009];
ll dp1[500009],dp2[500009];
set<int> used;
void DFS2(int u,int p)
{
    if(iss[u]) dp1[u] = 0;
    if(ist[u]) dp2[u] = 0;
    for(int i = 0;i < G2[u].size();i++)
    {
        int v = G2[u][i];
        if(v == p) continue;
        DFS2(v,u);
        dp1[u] = min(dp1[v]+d2[u][i],dp1[u]);
        dp2[u] = min(dp2[v]+d2[u][i],dp2[u]);
    }
    //cout << u << "_" << dp1[u] << "_" << dp2[u] << endl;
    ans = min(ans,dp1[u] + dp2[u]);

}
void DKS()
{
    int i;
    for(i = 0;i < s;i++)
    {
        iss[x[i]] = 1;
    }
    for(i = 0;i < t;i++)
    {
        ist[y[i]] = 1;
    }
    for(auto tt : used)
    {
        dp1[tt] = dp2[tt] = 10000000000000000;
    }
    DFS2(x[0],0);
    for(i = 0;i < s;i++)
    {
        iss[x[i]] = 0;
    }
    for(i = 0;i < t;i++)
    {
        ist[y[i]] = 0;
    }

}
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 DFS2(int, int)':
factories.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0;i < G2[u].size();i++)
      |                   ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:161:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = 0;i < vs.size();i++)
      |                   ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 47852 KB Output is correct
2 Correct 1669 ms 57048 KB Output is correct
3 Correct 1759 ms 56944 KB Output is correct
4 Correct 1712 ms 57068 KB Output is correct
5 Correct 1443 ms 57208 KB Output is correct
6 Correct 1340 ms 57164 KB Output is correct
7 Correct 1761 ms 56840 KB Output is correct
8 Correct 1731 ms 57008 KB Output is correct
9 Correct 1443 ms 57156 KB Output is correct
10 Correct 1261 ms 57196 KB Output is correct
11 Correct 1725 ms 56812 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 2758 ms 185200 KB Output is correct
3 Correct 3491 ms 186260 KB Output is correct
4 Correct 1988 ms 187624 KB Output is correct
5 Correct 3413 ms 211304 KB Output is correct
6 Correct 3654 ms 188332 KB Output is correct
7 Correct 3585 ms 84300 KB Output is correct
8 Correct 1871 ms 85212 KB Output is correct
9 Correct 2966 ms 88016 KB Output is correct
10 Correct 3505 ms 85516 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 47852 KB Output is correct
2 Correct 1669 ms 57048 KB Output is correct
3 Correct 1759 ms 56944 KB Output is correct
4 Correct 1712 ms 57068 KB Output is correct
5 Correct 1443 ms 57208 KB Output is correct
6 Correct 1340 ms 57164 KB Output is correct
7 Correct 1761 ms 56840 KB Output is correct
8 Correct 1731 ms 57008 KB Output is correct
9 Correct 1443 ms 57156 KB Output is correct
10 Correct 1261 ms 57196 KB Output is correct
11 Correct 1725 ms 56812 KB Output is correct
12 Correct 35 ms 47596 KB Output is correct
13 Correct 2758 ms 185200 KB Output is correct
14 Correct 3491 ms 186260 KB Output is correct
15 Correct 1988 ms 187624 KB Output is correct
16 Correct 3413 ms 211304 KB Output is correct
17 Correct 3654 ms 188332 KB Output is correct
18 Correct 3585 ms 84300 KB Output is correct
19 Correct 1871 ms 85212 KB Output is correct
20 Correct 2966 ms 88016 KB Output is correct
21 Correct 3505 ms 85516 KB Output is correct
22 Correct 7320 ms 199028 KB Output is correct
23 Correct 5689 ms 200360 KB Output is correct
24 Execution timed out 8068 ms 204744 KB Time limit exceeded
25 Halted 0 ms 0 KB -