Submission #95290

#	Time	Username	Problem	Language	Result	Execution time	Memory
95290		bogdan10bos	Factories (JOI14_factories)	C++14	100 / 100	3594 ms	190708 KiB

factories

#include <bits/stdc++.h>

//#define DEBUG

#ifndef DEBUG
#include "factories.h"
#endif // DEBUG

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

namespace Solver
{
    const int NMAX = 5e5;
    const int LG = 19;

    int N;
    LL ans;
    vector<LL> h;
    vector< vector<pii> > edg;
    int E, eul[NMAX + 5], lg2[2 * NMAX + 5], rmq[LG + 2][2 * NMAX + 5], itv[NMAX + 5][2];
    LL dst[NMAX + 5][2];
    vector< vector<int> > edg2;

    void DFS(int nod, int fth = 0)
    {
        rmq[0][++E] = nod;
        eul[nod] = E;
        itv[nod][0] = E;

        for(auto nxt: edg[nod])
            if(nxt.first != fth)
            {
                h[nxt.first] = h[nod] + nxt.second;
                DFS(nxt.first, nod);
                rmq[0][++E] = nod;
            }
        itv[nod][1] = E;
    }

    int minh(int a, int b)
    {
        if(h[a] < h[b]) return a;
        return b;
    }

    int LCA(int a, int b)
    {
        int pa = eul[a], pb = eul[b];
        if(pa > pb) swap(pa, pb);
        int pw = lg2[pb - pa + 1];
        return minh(rmq[pw][pa], rmq[pw][pb - (1 << pw) + 1]);
    }

    void init(int _N, int _A[], int _B[], int _D[])
    {
        N = _N;
        edg.resize(N + 2);
        edg2.resize(N + 2);
        for(int i = 0; i < N - 1; i++)
        {
            int x = _A[i], y = _B[i], z = _D[i];
            x++, y++;
            edg[x].push_back({y, z});
            edg[y].push_back({x, z});
        }

        h.resize(N + 2);
        DFS(1);

        for(int i = 2; i <= E; i++) lg2[i] = lg2[i >> 1] + 1;
        for(int i = 1; (1 << i) <= E; i++)
            for(int j = 1; j + (1 << i) - 1 <= E; j++)
                rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }

    void solve(int nod)
    {
        for(auto &nxt: edg2[nod])
        {
            solve(nxt);
            LL d = h[nxt] - h[nod];
            dst[nod][0] = min(dst[nod][0], dst[nxt][0] + d);
            dst[nod][1] = min(dst[nod][1], dst[nxt][1] + d);
        }
        ans = min(ans, dst[nod][0] + dst[nod][1]);
    }

    LL query(int A, int a[], int B, int b[])
    {
        vector<int> nodes;
        for(int i = 0; i < A; i++)  nodes.push_back(a[i] + 1);
        for(int i = 0; i < B; i++)  nodes.push_back(b[i] + 1);
        sort(nodes.begin(), nodes.end(),
             [](int a, int b) { return eul[a] < eul[b]; });
        vector<int> lcas;
        for(int i = 1; i < nodes.size(); i++)
            lcas.push_back(LCA(nodes[i], nodes[i - 1]));
        for(auto &x: lcas)  nodes.push_back(x);

        sort(nodes.begin(), nodes.end());
        nodes.erase( unique(nodes.begin(), nodes.end()), nodes.end() );
        sort(nodes.begin(), nodes.end(),
             [](int a, int b) { return eul[a] < eul[b]; });

        int root = nodes[0];
        for(auto &x: nodes) edg2[x].clear(), dst[x][0] = dst[x][1] = 1LL << 60;

        vector<int> stv;
        for(int i = 0; i < nodes.size(); i++)
        {
            int x = nodes[i];
            while(!stv.empty() && itv[stv.back()][1] < itv[x][0])
                stv.pop_back();
            if(!stv.empty() && itv[stv.back()][0] <= itv[x][0] && itv[x][1] <= itv[stv.back()][1])
                edg2[stv.back()].push_back(x);
            stv.push_back(x);
        }

        for(int i = 0; i < A; i++)  dst[ a[i] + 1 ][0] = 0;
        for(int i = 0; i < B; i++)  dst[ b[i] + 1 ][1] = 0;

        ans = 1LL << 60;
        solve(root);
        return ans;
    }
}

void Init(int N, int A[], int B[], int D[])
{
    Solver::init(N, A, B, D);
}

LL Query(int S, int X[], int T, int Y[])
{
    return Solver::query(S, X, T, Y);
}

#ifdef DEBUG
namespace Grader
{
    #include <stdio.h>
    #include <stdlib.h>

    #define MAX_N          500000
    #define MAX_Q          100000
    #define MAX_SUM_ST    1000000
    #define MAX_VALUE  1000000000

    static int N, Q;
    static int A[MAX_N], B[MAX_N], D[MAX_N];
    static int S[MAX_N];
    static int T[MAX_N];
    static int X[MAX_SUM_ST];
    static int Y[MAX_SUM_ST];

    static int Qx[MAX_N];
    static int Qy[MAX_N];

    int main() {
      freopen("1.in","r",stdin);

      int i, j, k;
      int STop, TTop;

      if (2 != scanf("%d%d", &N, &Q)) {
        fprintf(stderr, "error: cannot read N and Q.\n");
        exit(1);
      }
      if (!(2 <= N && N <= MAX_N)) {
        fprintf(stderr, "error: N is out of bounds.\n");
        exit(1);
      }
      if (!(1 <= Q && Q <= MAX_Q)) {
        fprintf(stderr, "error: Q is out of bounds.\n");
        exit(1);
      }
      for (i = 0; i < N - 1; ++i) {
        if (1 != scanf("%d", &A[i])) {
          fprintf(stderr, "error: cannot read A[%d].\n", i);
          exit(1);
        }
        if (!(0 <= A[i] && A[i] <= N - 1)) {
          fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
          exit(1);
        }
        if (1 != scanf("%d", &B[i])) {
          fprintf(stderr, "error: cannot read B[%d].\n", i);
          exit(1);
        }
        if (!(0 <= B[i] && B[i] <= N - 1)) {
          fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
          exit(1);
        }
        if (A[i] == B[i]) {
          fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
          exit(1);
        }
        if (1 != scanf("%d", &D[i])) {
          fprintf(stderr, "error: cannot read D[%d].\n", i);
          exit(1);
        }
        if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
          fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
          exit(1);
        }
      }

      STop = 0;
      TTop = 0;

      for (j = 0; j < Q; ++j) {
        if (2 != scanf("%d%d", &S[j], &T[j])) {
          fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
          exit(1);
        }

        if(STop + S[j] > MAX_SUM_ST) {
          fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
          exit(1);
        }

        if(TTop + T[j] > MAX_SUM_ST) {
          fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
          exit(1);
        }

        for (k = 0; k < S[j]; ++k, ++STop) {
          if (1 != scanf("%d", &X[STop])) {
            fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
            exit(1);
          }

          if (!(0 <= X[STop] && X[STop] <= N - 1)) {
            fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
            exit(1);
          }
        }

        for (k = 0; k < T[j]; ++k, ++TTop) {
          if (1 != scanf("%d", &Y[TTop])) {
            fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
            exit(1);
          }

          if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) {
            fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
            exit(1);
          }
        }
      }

      STop = 0;
      TTop = 0;
      Init(N, A, B, D);

      for (j = 0; j < Q; ++j) {
        for (k = 0; k < S[j]; k++) {
            Qx[k] = X[STop++];
        }
        for (k = 0; k < T[j]; k++) {
            Qy[k] = Y[TTop++];
        }

        printf("%lld\n", Query(S[j], Qx, T[j], Qy));
      }


      return 0;
    }
}

int main()
{
    Grader::main();
    return 0;
}
#endif

Compilation message (stderr)

factories.cpp: In function 'LL Solver::query(int, int*, int, int*)':
factories.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < nodes.size(); i++)
                        ~~^~~~~~~~~~~~~~
factories.cpp:112:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < nodes.size(); i++)
                        ~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67