제출 #1324109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324109		sh_qaxxorov_571	Examination (JOI19_examination)	C++20	컴파일 에러	0 ms	0 KiB

examination

#include "factories.h"
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

// Graf va yordamchi massivlar
vector<pair<int, int>> adj[500005];
int sz[500005], parent[500005];
bool visited[500005];
ll best_dist[500005]; 

// Masofalarni hisoblash uchun (LCA + Depth)
ll depth[500005];
int up[500005][20], tin[500005], tout[500005], timer;

// Daraxt xususiyatlarini aniqlash (DFS)
void dfs_lca(int u, int p, ll d) {
    tin[u] = ++timer;
    depth[u] = d;
    up[u][0] = p;
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto& edge : adj[u]) {
        if (edge.first != p) dfs_lca(edge.first, u, d + edge.second);
    }
    tout[u] = timer;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int get_lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = 19; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

ll get_dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[get_lca(u, v)];
}

// Sentroidni topish funksiyalari
int get_sz(int u, int p) {
    sz[u] = 1;
    for (auto& edge : adj[u]) {
        if (edge.first != p && !visited[edge.first]) sz[u] += get_sz(edge.first, u);
    }
    return sz[u];
}

int get_centroid(int u, int p, int n) {
    for (auto& edge : adj[u]) {
        if (edge.first != p && !visited[edge.first] && sz[edge.first] > n / 2)
            return get_centroid(edge.first, u, n);
    }
    return u;
}

void decompose(int u, int p) {
    int n = get_sz(u, -1);
    int centroid = get_centroid(u, -1, n);
    visited[centroid] = true;
    parent[centroid] = p;
    for (auto& edge : adj[centroid]) {
        if (!visited[edge.first]) decompose(edge.first, centroid);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs_lca(0, 0, 0);
    decompose(0, -1);
    for (int i = 0; i < N; i++) best_dist[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> modified_centroids;
    
    // X to'plamini sentroid daraxtiga joylashtirish
    for (int i = 0; i < S; i++) {
        int curr = X[i];
        while (curr != -1) {
            best_dist[curr] = min(best_dist[curr], get_dist(X[i], curr));
            modified_centroids.push_back(curr);
            curr = parent[curr];
        }
    }

    ll ans = INF;
    // Y to'plami orqali eng qisqa masofani topish
    for (int i = 0; i < T; i++) {
        int curr = Y[i];
        while (curr != -1) {
            ans = min(ans, get_dist(Y[i], curr) + best_dist[curr]);
            curr = parent[curr];
        }
    }

    // Massivni tozalash
    for (int c : modified_centroids) best_dist[c] = INF;
    
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp:1:10: fatal error: factories.h: No such file or directory
    1 | #include "factories.h"
      |          ^~~~~~~~~~~~~
compilation terminated.