Submission #1135613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135613		Joseph0121	September (APIO24_september)	C++20	100 / 100	284 ms	38440 KiB

september

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int mod = 1e9+7;
#define vt vector


int N,M;

int solve(int n, int m, vector<int> p, vector<vector<int>> vv){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	N = n; M = m;
	vt<vt<vt<int>>> e(m,vt<vt<int>>(N+1));
	vt<vt<int>> indeg(m,vt<int>(N+1,0)), indeg2(m,vt<int>(N+1,0));
	vt<vt<int>> arr(m,vt<int>(N+1));
	vector<set<vector<int>>> s(M);
	vector<int> hash(M,1);
	for(int i = 0;i<N;i++){
		int x = p[i];
		if(i == 0) continue;
		for(int j = 0;j<M;j++){
			e[j][i].push_back(x);
			indeg[j][x]++;
		}
	}
			for(int i = 0;i<M;i++){
			for(int j = 0;j<N-1;j++){
				arr[i][j] = vv[i][j];
			}
		}
	
	int ans = 0;
	for(int i = 0;i<N-1;i++){
		bool flag = true;
		for(int j = 0;j<M;j++){
			hash[j] = (long long)hash[j]*((long long)arr[j][i]*123+7)%(long long)mod;
			indeg2[j][arr[j][i]] = indeg[j][arr[j][i]];
			s[j].insert({indeg[j][arr[j][i]],arr[j][i]});
			while(s[j].size()){
				vector<int> v = *s[j].begin();
				// cout<<v[0]<<" "<<v[1]<<endl;
				if(v[0]!=0) break;
				s[j].erase(s[j].begin());
				for(auto k: e[j][v[1]]){
					indeg[j][k]-=1;
					if(indeg[j][k] == 0){
						auto it = s[j].find({indeg2[j][k],k});
						if(it != s[j].end()){ //when already add
							// cout<<"node: "<<arr[j][i]<<endl;
							vector<int> v2 = *it;
							s[j].erase(it);
							v2[0] = 0;
							s[j].insert(v2);
						}
					}
				}
			}
		}
		//check if everyone if 0
		for(int j = 0;j<M;j++){
			// cout<<s[j].size()<<" ";
			if(s[j].size()) flag = false;
		}
		// cout<<"nxt"<<endl;
		if(flag){
			bool flag2 = true;
			for(int j = 1;j<M;j++){ if(hash[j]!=hash[j-1]){
				flag2 = false;
			}}
			if(flag2){
				ans++;
				for(int j = 0;j<M;j++) hash[j] = 1;
			}
			
			
		}
	}
	// cout<<endl;
	// cout<<s[0].size()<<" "<<s[1].size()<<endl;
	return ans;
}

// int main() {
// 	cout<<solve(5,2,{-1, 0, 0, 1, 1},{{1,2,3,4},{4,1,2,3}});

	
	
// 	return 0;
// }

• 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