Submission #859834

#	Time	Username	Problem	Language	Result	Execution time	Memory
859834		serifefedartar	Hop (COCI21_hop)	C++17	110 / 110	27 ms	5468 KiB

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 / 10
• Subtask 2: 100 / 100