Submission #1018367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018367		MohamedFaresNebili	September (APIO24_september)	C++17	100 / 100	115 ms	20812 KiB

september

#include <bits/stdc++.h>

		using namespace std;

		vector<int> adj[100005];
		int par[100005];
		int lo[100005], hi[100005];

		int findSet(int v) {
			if(par[v] == v) return v;
			return par[v] = findSet(par[v]);
		}
		void unionSet(int u, int v) {
			u = findSet(u), v = findSet(v);
			if(u == v) return;
			par[u] = v;
			lo[v] = min(lo[v], lo[u]);
			hi[v] = max(hi[v], hi[u]);
		}

		void dfs(int v) {
			for(auto u : adj[v]) {
				dfs(u);
				hi[v] = max(hi[v], hi[u]);
			}
		}

		int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
			for(int l = 0; l < N; l++) {
				adj[l].clear(), par[l] = l;
				lo[l] = N, hi[l] = 0;
			}

			for(int l = 1; l < N; l++) 
				adj[F[l]].push_back(l);
			
			for(int i = 0; i < M; i++)
				for(int l = 0; l < N - 1; l++) {
					lo[S[i][l]] = min(lo[S[i][l]], l);
					hi[S[i][l]] = max(hi[S[i][l]], l);
				}

			dfs(0);

			int res = 0;

			for(int i = 0; i < M; i++) {
				for(int l = 0; l < N - 1; l++) {
					if(lo[S[i][l]] < l)
						unionSet(S[i][l], S[i][l - 1]);
					if(hi[S[i][l]] > l)
						unionSet(S[i][l], S[i][l + 1]);
				}
			}
			for(int l = 1; l < N; l++)
				if(par[l] == l) ++res;
			

			return res;
		}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16