oj.uz

답안 #872073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872073 2023-11-12T09:04:58 Z iliaaaaa 공장들 (JOI14_factories) C++14
0 / 100
 10 ms 20828 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define len(x) (int) x.size()
#define pb push_back
mt19937 rnd(time(0));

const int N = 1e5 + 7;
const ll INF = 1e16;
bool mark1[N], mark2[N];
vector<pii> adj[N];
vector<int> S, T;
ll dis[N];
int n, q;

void Init(int N, int A[], int B[], int D[]) {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].pb({B[i], D[i]});
		adj[B[i]].pb({A[i], D[i]});
	}
}

ll Query(int s, int X[], int t, int Y[]) {
	S.clear(), T.clear();
	for (int i = 0; i < s; i++)
		S.pb(X[i]);
	for (int i = 0; i < t; i++)
		T.pb(Y[i]);
	if (len(S) > len(T))
		swap(S, T);
	for (int u: S)
		mark1[u] = true;
	for (int u: T)
		mark2[u] = true;
	for (int u: S) 
		if (mark1[u] && mark2[u]) {
			for (int v: S)
				mark1[v] = false;
			for (int v: T)
				mark2[v] = false;
			return 0;
		}
	queue<int> q;
	for (int u: S) {
		dis[u] = 0;
		q.push(u);
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (mark2[u]) 
			continue;
		for (auto [v, w]: adj[u])
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				q.push(v);
			}
	}
	ll ans = INF;
	for (int u: T)
		ans = min(ans, dis[u]);
	for (int i = 0; i < n; i++)
		dis[i] = INF;
	for (int u: S)
		mark1[u] = false;
	for (int u: T)
		mark2[u] = false;
	return ans;
}

Compilation message

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:61:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   for (auto [v, w]: adj[u])
      |             ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 20828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -