답안 #95290 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95290	2019-01-29T17:28:37 Z	bogdan10bos	공장들 (JOI14_factories)	C++14	100 / 100	3594 ms	190708 KB

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

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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	1016 KB	Output is correct
2	Correct	843 ms	15352 KB	Output is correct
3	Correct	858 ms	15360 KB	Output is correct
4	Correct	861 ms	15880 KB	Output is correct
5	Correct	818 ms	15804 KB	Output is correct
6	Correct	666 ms	15504 KB	Output is correct
7	Correct	868 ms	15640 KB	Output is correct
8	Correct	877 ms	15636 KB	Output is correct
9	Correct	828 ms	15836 KB	Output is correct
10	Correct	664 ms	15480 KB	Output is correct
11	Correct	853 ms	15372 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	760 KB	Output is correct
2	Correct	1515 ms	152780 KB	Output is correct
3	Correct	1667 ms	155892 KB	Output is correct
4	Correct	1197 ms	153172 KB	Output is correct
5	Correct	1707 ms	190236 KB	Output is correct
6	Correct	2060 ms	157040 KB	Output is correct
7	Correct	1377 ms	41796 KB	Output is correct
8	Correct	1097 ms	41964 KB	Output is correct
9	Correct	1409 ms	47984 KB	Output is correct
10	Correct	1366 ms	42888 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	1016 KB	Output is correct
2	Correct	843 ms	15352 KB	Output is correct
3	Correct	858 ms	15360 KB	Output is correct
4	Correct	861 ms	15880 KB	Output is correct
5	Correct	818 ms	15804 KB	Output is correct
6	Correct	666 ms	15504 KB	Output is correct
7	Correct	868 ms	15640 KB	Output is correct
8	Correct	877 ms	15636 KB	Output is correct
9	Correct	828 ms	15836 KB	Output is correct
10	Correct	664 ms	15480 KB	Output is correct
11	Correct	853 ms	15372 KB	Output is correct
12	Correct	4 ms	760 KB	Output is correct
13	Correct	1515 ms	152780 KB	Output is correct
14	Correct	1667 ms	155892 KB	Output is correct
15	Correct	1197 ms	153172 KB	Output is correct
16	Correct	1707 ms	190236 KB	Output is correct
17	Correct	2060 ms	157040 KB	Output is correct
18	Correct	1377 ms	41796 KB	Output is correct
19	Correct	1097 ms	41964 KB	Output is correct
20	Correct	1409 ms	47984 KB	Output is correct
21	Correct	1366 ms	42888 KB	Output is correct
22	Correct	2628 ms	161260 KB	Output is correct
23	Correct	2610 ms	161992 KB	Output is correct
24	Correct	3061 ms	165740 KB	Output is correct
25	Correct	2986 ms	167348 KB	Output is correct
26	Correct	2865 ms	159380 KB	Output is correct
27	Correct	3594 ms	190708 KB	Output is correct
28	Correct	2219 ms	159736 KB	Output is correct
29	Correct	3142 ms	158020 KB	Output is correct
30	Correct	2987 ms	157260 KB	Output is correct
31	Correct	2642 ms	157716 KB	Output is correct
32	Correct	1505 ms	47528 KB	Output is correct
33	Correct	1161 ms	41424 KB	Output is correct
34	Correct	1365 ms	38148 KB	Output is correct
35	Correct	1529 ms	38084 KB	Output is correct
36	Correct	1666 ms	38924 KB	Output is correct
37	Correct	1689 ms	38900 KB	Output is correct

답안 #95290

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0