Submission #872073

#	Time	Username	Problem	Language	Result	Execution time	Memory
872073		iliaaaaa	Factories (JOI14_factories)	C++14	0 / 100	10 ms	20828 KiB

factories

#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 (stderr)

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67