Submission #859834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
859834	2023-10-10T19:05:04 Z	serifefedartar	Hop (COCI21_hop)	C++17	110 / 110	27 ms	5468 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 22; 
const ll MAXN = 1005;

vector<ll> v;
set<int> graph[MAXN]; 
int ans[MAXN][MAXN], dist[MAXN];
void dfs(int node, int frog) {
	if (dist[node] == 3)
		return ;

	vector<int> omit;
	for (auto u : graph[node]) {
		if (dist[u] == -1) {
			dist[u] = dist[node] + 1;
			omit.push_back(u);
			dfs(u, frog);
		} else if (dist[u] >= dist[node] + 1)
			omit.push_back(u);
	}

	for (auto u : omit) {
		ans[node][u] = frog;
		graph[node].erase(u);
	}
}

int main() {
	fast
	int n;
	cin >> n;

	v = vector<ll>(n+1);
	for (int i = 1; i <= n; i++)
		cin >> v[i];

	for (int i = 1; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			if (v[j] % v[i] == 0)
				graph[i].insert(j);
			else
				ans[i][j] = 1;
		}
	}

	for (int rep = 0; rep < 30; rep++) {
		for (int frog = 1; frog <= 3; frog++) {
			memset(dist, -1, sizeof(dist)); 
			for (int node = 1; node <= n; node++) {
				if (dist[node] == -1) {
					dist[node] = 0;
					dfs(node, frog);
				}
			}
		}
	}

	for (int i = 1; i <= n-1; i++) {
		for (int j = 1; j <= i; j++)
			cout << ans[j][i+1] << " ";
		cout << "\n";
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct

Subtask #2

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	27 ms	5460 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	1 ms	2652 KB	Output is correct
11	Correct	27 ms	5204 KB	Output is correct
12	Correct	26 ms	5468 KB	Output is correct
13	Correct	24 ms	5204 KB	Output is correct
14	Correct	2 ms	2908 KB	Output is correct
15	Correct	24 ms	5204 KB	Output is correct
16	Correct	26 ms	5464 KB	Output is correct
17	Correct	26 ms	5204 KB	Output is correct
18	Correct	26 ms	5456 KB	Output is correct
19	Correct	26 ms	5316 KB	Output is correct
20	Correct	26 ms	5212 KB	Output is correct
21	Correct	24 ms	5212 KB	Output is correct
22	Correct	24 ms	5212 KB	Output is correct
23	Correct	26 ms	5392 KB	Output is correct