Submission #994315

#	Time	Username	Problem	Language	Result	Execution time	Memory
994315		Halym2007	September (APIO24_september)	C++17	100 / 100	134 ms	13000 KiB

september

#include <bits/stdc++.h>
#include "september.h"
using namespace std;
#define ff first
#define ss second
#define sz size()
#define pb push_back
#define ll long long
#define pii pair <int, int>
const int AA = 1e5 + 5;

int par[AA], deg[AA];

bool vis[AA];
multiset <int> s;
vector <int> v[AA];

void ugrat (int x, int y) {
	vis[x] = 1;
	for (int i = 1; i <= y; ++i) s.insert (x);
	for (int i : v[x]) {
		if (par[x] == i or vis[i]) continue;
		ugrat (i, y);
	}
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	par[0] = -1;
	for (int i = 1; i < N; ++i) {
		par[i] = F[i];
		v[i].pb (F[i]);
		v[F[i]].pb (i);
		
	}
	int jogap = 0;
	for (int k = 0; k <= N - 2; ++k) {
		for (int i = 0; i < M; ++i) {
			int j = S[i][k];
			jogap++;
			ugrat (j, M);
			int val = k;
			while (!s.empty()) {
				for (int j = 0; j < M; ++j) {
					if (s.find (S[j][val]) == s.end ()) {
						if (!vis[S[j][val]]) {
							ugrat (S[j][val], M);
							s.erase (s.find (S[j][val]));
						}
					}
					else {
						s.erase (s.find (S[j][val]));
					}
				}
				val++;
			}		
			k = val - 1;
			break;
		}
	} 
	s.clear();
	for (int i = 0; i < N; ++i) {
		v[i].clear();
		vis[i] = 0;
	}
	return jogap;
}


//void taskcase() {
//	int N, M;
//	assert(2 == scanf("%d%d", &N, &M));
//	std::vector<int> F(N);
//	F[0] = -1;
//	for (int i = 1; i < N; ++i)
//  		assert(1 == scanf("%d", &F[i]));
//	
//	std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
//	for (int i = 0; i < M; ++i)
//		for (int j = 0; j < N - 1; ++j)
//  			assert(1 == scanf("%d", &S[i][j]));
//  	
//	printf("%d\n", solve(N, M, F, S));
//}
//
//int main() {
//	freopen ("input.txt", "r", stdin);
//	int T;
//	assert(1 == scanf("%d", &T));
//	while(T--) taskcase();
//	return 0;
//}
//
///*
//1
//3 1
//0 0
//1 2
//ans : 2
//*/
///*
//1
//5 2
//0 0 1 1
//1 2 3 4
//4 1 2 3
//ans : 1
//*/

• 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