Submission #1361236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361236		po_rag526	Tour (BOI25_tou)	C++20	0 / 100	307 ms	720532 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int M = 1e6 + 5;
int u[M];
int v[M];
int col[M];

struct edgelord
{
	deque <int> L;

	void add_edge(int id)
	{
		L.push_back(id);
	}

	void prepare()
	{
		sort(L.begin(), L.end(), [] (int i, int j) { return col[i] < col[j]; });
	}

	void clear()
	{
		L.clear();
	}

	int get_edge(int c)
	{
		if (L.empty()) return 0;
		int f = L.front();
		int b = L.back();
		if (col[f] != c) { L.pop_front(); return f; }
		if (col[b] != c) { L.pop_back(); return b; }
		return 0;
	}
};

edgelord E[N];
set <int> S[N];
vector <int> out;

int dfs(int e)
{
	//printf("dfs in %d\n", e);

	S[u[e]].insert(e);

	// check for edges on the stack
	for (int p : S[v[e]]){
		if (col[p] != col[e]){
			out.push_back(e);
			return p;
		}
	}

	// recurse
	while (true){
		int f = E[v[e]].get_edge(col[e]);
		if (f == 0) break;
		int res = dfs(f);
		if (res == 0) continue;
		if (res == -1) return -1;
		out.push_back(e);
		if (res == e) return -1;
		return res;
	}

	S[u[e]].erase(e);
	//printf("dfs out  %d\n", e);
	return 0;
}

void solve()
{
	int n, m;
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; i++){
		E[i].clear();
		S[i].clear();
	}
	out.clear();

	for (int i = 1; i <= m; i++){
		scanf("%d%d%d", &u[i], &v[i], &col[i]);
		E[u[i]].add_edge(i);
	}
	
	for (int i = 1; i <= n; i++) E[i].prepare();

	for (int i = 1; i <= n; i++){
		while (true) {
			int e = E[i].get_edge(0);
			if (e == 0) break;
			if (dfs(e) == true) {
				break;
			}
		}
		if (!out.empty()) break;
	}

	if (out.empty()) {
		printf("NO\n");
	} else {
		printf("YES\n%d ", (int)(out.size()));
		reverse(out.begin(), out.end());
		for (int x : out) {
			printf("%d ", x);
		}
		printf("\n");
	}
}

int main()
{
	int q;
	scanf("%d", &q);
	while (q--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 scanf("%d%d%d", &u[i], &v[i], &col[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 23
• Subtask 4: 0 / 19
• Subtask 5: 0 / 25
• Subtask 6: 0 / 24