QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472828#8873. KeysPetroTarnavskyi#Compile Error//C++203.8kb2024-07-11 19:39:092024-07-11 19:39:09

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 19:39:09]
  • 评测
  • [2024-07-11 19:39:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 100'447;
VI g[N];
bool used[N];
int from[N];
int p[N];
map<PII, int> mp;

void dfs1(int v)
{
	used[v] = true;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			from[to] = v;
			dfs1(to);
		}
	}
}

int dfs2(int v, int par = -1)
{
	p[v] = par;
	for (auto to : g[v])
	{
		if (to == par)
			continue;
		if (to == 1)
			return v;
		int res = dfs2(to, v);
		if (res != -1)
			return res;
	}
	return -1;
}

void printKeys(const VI& v) 
{
	FOR (i, 0, SZ(v))
	{
		if (i)
			cout << ' ';
		cout << v[i];
	}
	cout << '\n';
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	FOR (i, 0, m)
	{
		int a, b;
		cin >> a >> b;
		mp[{a, b}] = i;
		mp[{b, a}] = i;
		g[a].PB(b);
		g[b].PB(a);
	}
	used[1] = true;
	dfs1(0);
	int cnt = 0;
	for (auto to : g[1])
	{
		if (used[to])
			cnt++;
	}
	if (cnt >= 2)
	{
		int u = -1;
		for (auto to : g[1])
		{
			if (used[to])
				u = to;
		}
		int U = u;
		VI path = {1, u};
		while (u != 0)
		{
			u = from[u];
			path.PB(u);
		}
		set<int> marichka;
		FOR (i, 0, SZ(path) - 1)
		{
			marichka.insert(mp[{path[i], path[i + 1]}]);
		}
		VI zenyk;
		FOR (i, 0, m)
			if (!marichka.count(i))
				zenyk.PB(i);
		reverse(ALL(path));
		VI mar(ALL(marichka));
		
		printKeys(mar);
		printKeys(zenyk);
		
		FOR (i, 1, SZ(path))
		{
			cout << "MOVE " << path[i] << '\n';
			if (i + 1 != SZ(path))
				cout << "DROP " << mp[{path[i - 1], path[i]}] << '\n';
		}
		cout << "DONE\n";
		path.clear();
		int v = -1;
		for (auto to : g[1])
		{
			if (used[to] && to != U)
				v = to;
		}
		path = {1, v};
		while (v != 0)
		{
			v = from[v];
			path.PB(v);
		}
		FOR (i, 0, SZ(path) - 1)
		{
			int k = mp[{path[i], path[i + 1]}];
			if (marichka.count(k))
				cout << "GRAB\n";
			cout << "MOVE " << path[i + 1] << '\n';
		}
		cout << "DONE\n";
	}
	else
	{
		if (cnt == 0)
		{
			cout << "No solution\n";
			return 0;
		}
		int v = dfs2(1);
		if (v == -1)
		{
			cout << "No solution\n";
			return 0;
		}
		VI cycle = { 1, v };
		while (v != 1)
		{
			v = p[v];
			cycle.PB(v);
		}
		reverse(ALL(cycle));
		
		int u = -1;
		for (auto to : g[1])
		{
			if (used[to])
				u = to;
		}
		VI path = {1, u};
		while (u != 0)
		{
			u = from[u];
			path.PB(u);
		}
		reverse(ALL(path));
		set<int> marichka;
		FOR (i, 0, SZ(path) - 1)
		{
			marichka.insert(mp[{path[i], path[i + 1]}]);
		}
		marichka.insert(mp[{1, v}]);
		
		VI zenyk;
		FOR (i, 0, m)
			if (!marichka.count(i))
				zenyk.PB(i);
		VI mar(ALL(marichka));
		
		printKeys(mar);
		printKeys(zenyk);
		
		FOR (i, 1, SZ(path))
		{
			cout << "MOVE " << path[i] << '\n';
			if (i + 1 != SZ(path))
				cout << "DROP " << mp[{path[i - 1], path[i]}] << '\n';
		}
		cout << "MOVE " << v << '\n';
		cout << "DROP " << mp[{1, u}] << '\n';
		cout << "MOVE " << 1 << '\n';
		cout << "DONE\n";
		
		FOR (i, 1, SZ(cycle) - 1)
		{
			cout << "MOVE " << cycle[i] << '\n';
		}
		cout << "GRAB\n";
		RFOR (i, SZ(cycle) - 2, 0)
			cout << "MOVE " << cycle[i] << '\n';
		RFOR (i, SZ(path), 0)
		{
			cout << "GRAB\n";
			cout << "MOVE " << path[i] << '\n';
		}
		cout << "DONE\n";
		
		
	}
	
	return 0;
}

0
1 2 3 4
MOVE 1
MOVE 1
DROP 0
MOVE 1
DONE
MOVE 2
MOVE 3
MOVE 4
GRAB
MOVE 3
MOVE 2
MOVE 1
GRAB
MOVE 1
GRAB
MOVE 0
DONE

詳細信息

answer.code:231:1: error: expected unqualified-id before numeric constant
  231 | 0
      | ^