oj.uz

Submission #900094

# Submission time Handle Problem Language Result Execution time Memory
900094 2024-01-07T15:51:36 Z yellowtoad Factories (JOI14_factories) C++17
100 / 100
 5285 ms 237860 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
 
long long n, dist[500010], depth[500010], ord[500010], p[500010][20], cnt, dp[500010], node[500010], par[500010], lst, minn;
vector<pair<long long,long long>> edge[500010], nodes, stack;
vector<int> stk, hv, adj[500010];
 
void dfs1(int u, int v, long long _dist, int _depth) {
    dist[u] = _dist;
    depth[u] = _depth;
    p[u][0] = v;
    ord[u] = ++cnt;
    for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
    for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n-1; i++) {
        edge[A[i]+1].push_back({B[i]+1,D[i]});
        edge[B[i]+1].push_back({A[i]+1,D[i]});
    }
    for (int i = 0; i <= n; i++) dp[i] = 1e18;
    dfs1(1,0,0,1);
}
 
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u,v);
    int i = 19;
    while (i >= 0) {
        if (depth[p[v][i]] >= depth[u]) v = p[v][i];
        i--;
    }
    if (u == v) return u;
    i = 19;
    while (i >= 0) {
        if (p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
        i--;
    }
    return p[u][0];
}
 
void dfs2(int u) {
    if (node[u] == 1) dp[u] = dist[u];
    for (int i = 0; i < adj[u].size(); i++) {
        dfs2(adj[u][i]);
        dp[u] = min(dp[u],dp[adj[u][i]]);
    }
}
 
void dfs3(int u) {
    if (dp[u] != 1e18) dp[u] = (long long)1e17+dp[u]-2*dist[u];
    for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
}
 
void dfs4(int u) {
    if (node[u] == 2) minn = min(minn,stack.back().f-(long long)1e17+dist[u]);
    for (int i = 0; i < adj[u].size(); i++) {
        if (stack.back().f >= dp[adj[u][i]]) stack.push_back({dp[adj[u][i]],adj[u][i]});
        else stack.push_back(stack.back());
        dfs4(adj[u][i]);
        stack.pop_back();
    }
}
 
long long Query(int S, int X[], int T, int Y[]) {
    minn = 1e18;
    for (int i = 0; i < S; i++) {
        node[X[i]+1] = 1;
        nodes.push_back({ord[X[i]+1],X[i]+1});
    }
    for (int i = 0; i < T; i++) {
        node[Y[i]+1] = 2;
        nodes.push_back({ord[Y[i]+1],Y[i]+1});
    }
    sort(nodes.begin(),nodes.end());
    for (int i = 0; i < nodes.size(); i++) {
        if (stk.size()) {
            int u = lca(nodes[i].s,stk.back());
            while (stk.size() && (lca(u,stk.back()) == u)) {
                lst = stk.back();
                hv.push_back(lst);
                stk.pop_back();
                if (stk.size()) par[lst] = stk.back();
            }
            if (lst == u) hv.pop_back();
            else par[lst] = u;
            stk.push_back(u);
        } 
        stk.push_back(nodes[i].s);
    }
    while (stk.size()) {
        lst = stk.back();
        stk.pop_back();
        hv.push_back(lst);
        if (stk.size()) par[lst] = stk.back();
    }
    for (int i = 0; i < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
    dfs2(0);
    dfs3(0);
    stack.push_back({dp[0],0});
    dfs4(0);
    for (int i = 0; i < S; i++) node[X[i]+1] = 0;
    for (int i = 0; i < T; i++) node[Y[i]+1] = 0;
    for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
    adj[0].clear();
    dp[0] = 1e18;
    nodes.clear();
    hv.clear();
    stk.clear();
    stack.clear();
    return minn;
}

Compilation message

factories.cpp: In function 'void dfs1(int, int, long long int, int)':
factories.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
      |                     ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int)':
factories.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs3(int)':
factories.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs4(int)':
factories.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < nodes.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
factories.cpp:103:23: 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 < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
      |                     ~~^~~~~~~~~~~
factories.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
      |                     ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 54108 KB Output is correct
2 Correct 1173 ms 68860 KB Output is correct
3 Correct 1297 ms 68748 KB Output is correct
4 Correct 1195 ms 68948 KB Output is correct
5 Correct 1081 ms 69092 KB Output is correct
6 Correct 970 ms 68692 KB Output is correct
7 Correct 1319 ms 68692 KB Output is correct
8 Correct 1194 ms 69016 KB Output is correct
9 Correct 1107 ms 69100 KB Output is correct
10 Correct 966 ms 68696 KB Output is correct
11 Correct 1293 ms 68696 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 54104 KB Output is correct
2 Correct 1591 ms 193408 KB Output is correct
3 Correct 3172 ms 197048 KB Output is correct
4 Correct 1045 ms 190496 KB Output is correct
5 Correct 2693 ms 232236 KB Output is correct
6 Correct 3089 ms 197968 KB Output is correct
7 Correct 2431 ms 95032 KB Output is correct
8 Correct 1184 ms 93888 KB Output is correct
9 Correct 2359 ms 100776 KB Output is correct
10 Correct 2211 ms 95900 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 54108 KB Output is correct
2 Correct 1173 ms 68860 KB Output is correct
3 Correct 1297 ms 68748 KB Output is correct
4 Correct 1195 ms 68948 KB Output is correct
5 Correct 1081 ms 69092 KB Output is correct
6 Correct 970 ms 68692 KB Output is correct
7 Correct 1319 ms 68692 KB Output is correct
8 Correct 1194 ms 69016 KB Output is correct
9 Correct 1107 ms 69100 KB Output is correct
10 Correct 966 ms 68696 KB Output is correct
11 Correct 1293 ms 68696 KB Output is correct
12 Correct 13 ms 54104 KB Output is correct
13 Correct 1591 ms 193408 KB Output is correct
14 Correct 3172 ms 197048 KB Output is correct
15 Correct 1045 ms 190496 KB Output is correct
16 Correct 2693 ms 232236 KB Output is correct
17 Correct 3089 ms 197968 KB Output is correct
18 Correct 2431 ms 95032 KB Output is correct
19 Correct 1184 ms 93888 KB Output is correct
20 Correct 2359 ms 100776 KB Output is correct
21 Correct 2211 ms 95900 KB Output is correct
22 Correct 3026 ms 204924 KB Output is correct
23 Correct 2796 ms 205404 KB Output is correct
24 Correct 4081 ms 210368 KB Output is correct
25 Correct 4273 ms 212364 KB Output is correct
26 Correct 5285 ms 204188 KB Output is correct
27 Correct 4185 ms 237860 KB Output is correct
28 Correct 1775 ms 200556 KB Output is correct
29 Correct 5244 ms 202936 KB Output is correct
30 Correct 5218 ms 203016 KB Output is correct
31 Correct 5026 ms 203180 KB Output is correct
32 Correct 2001 ms 105508 KB Output is correct
33 Correct 1305 ms 97400 KB Output is correct
34 Correct 1794 ms 94496 KB Output is correct
35 Correct 1792 ms 94484 KB Output is correct
36 Correct 2190 ms 95544 KB Output is correct
37 Correct 2440 ms 95032 KB Output is correct