Submission #1160881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160881		sleepntsheep	Drivers (BOI24_drivers)	C++20	100 / 100	181 ms	57928 KiB

Main

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int N = 999999;

struct edge {
	int w, v, u;
	bool operator<(const edge &o) const {
		return w < o.w;
	}
};

std::vector<int> g[N];
int n, m, u, l, when[N], par[N], ds[N];
edge *e;

void input() {
	scanf("%d%d%d", &n, &m, &u);
	e = new edge[m + n - 1];
	for (int i = 0; i < m; ++i)
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	for (int i = 2; i <= n; ++i) {
		edge r = {1000000001, i, i - 1};
		e[m++] = r;
	}
	std::sort(e, e + m);
}

int ds_find(int i) {
	if (ds[i] == i)
		return i;
	return ds[i] = ds_find(ds[i]);
}

struct {
	void build() {
		for(int i=0;i<N;++i)par[i]=ds[i]=i;
		l = n;

		for (auto *ed = e; ed < e + m; ++ed) {
			auto [w, v, u] = *ed;
			v = ds_find(v);
			u = ds_find(u);
			if (u == v)
				continue;

			++l;
			ds[v] = ds[u] = l;
			par[v] = par[u] = l;
			g[l].push_back(u);
			g[l].push_back(v);
			when[l] = w;
		}
	}
} krt;

struct {
	int tin[N], head[N], sz[N], timer, dep[N];

	void dfs(int u) {
		sz[u] = 1;
		for (int i = 0; i < g[u].size(); ++i) {
			dfs(g[u][i]);
			sz[u] += sz[g[u][i]];
			if (sz[g[u][i]] > sz[g[u][0]])
				std::swap(g[u][0], g[u][i]);
		}
	}

	void hld(int u, int hd) {
		tin[u] = timer++;
		head[u] = hd;
		for (auto v : g[u])
			dep[v] = dep[u] + 1, hld(v, v == g[u][0] ? hd : v);
	}

	int lca(int u, int v) {
		while (head[u] != head[v]) {
			if (dep[head[u]] < dep[head[v]])
				std::swap(u, v);
			u = par[head[u]];
		}
		return dep[u] > dep[v] ? v : u;
	}

	void build() {
		dfs(l);
		hld(l, l);
	}
} lca;

struct {
	void query() {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		int x = lca.lca(a, b);
		if (when[x] <= c)
			puts("TAIP");
		else
			puts("NE");
	}

	void queries() {
		while (u--)
			query();
	}
} miku;

int main() {
	input();
	krt.build();
	lca.build();
	miku.queries();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void input()':
Main.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d%d%d", &n, &m, &u);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'void<unnamed struct>::query()':
Main.cpp:97:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |                 scanf("%d%d%d", &a, &b, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45