제출 #48345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48345		maksim_gaponov	공장들 (JOI14_factories)	C++14	0 / 100	6091 ms	214752 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MAXN = 5e3 + 10;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
//int type[MAXN];
ll dist[MAXN][MAXN];
bool used[MAXN];

void dfs(int u, int w) {
    used[u] = true;
    for (auto v : g[u]) {
        if (!used[v.first]) {
            dist[w][v.first] = dist[w][u] + v.second;
            dfs(v.first, w);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    IOoptimize();
    n = N;
    for (int i = 0; i < n - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    for (int i = 0; i < n; i++) {
        memset(used, 0, sizeof(used));
        dfs(i, i);
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    //memset(type, 0, sizeof(type));
    /*for (int i = 0; i < S; i++) {
        type[X[i]] = 1;
    }
    for (int i = 0; i < T; i++) {
        type[Y[i]] = -1;
    }*/
    ll ans = INF;
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < T; j++) {
            ans = min(ans, dist[X[i]][Y[j]]);
        }
    }
    return ans;
}

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