Submission #1135611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135611		Joseph0121	September (APIO24_september)	C++20	100 / 100	271 ms	38424 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<bool>> visited(M,vt<bool>(N+1,0));
	vt<vt<int>> arr(m,vt<int>(N+1));
	vector<deque<vector<int>>> s(M);
	vector<int> cnt(M,0), 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++){
			cnt[j]++;
			queue<vector<int>> q;
			q.push({indeg[j][arr[j][i]],arr[j][i]});
			hash[j] = (long long)hash[j]*((long long)arr[j][i]*123+7)%(long long)mod;
			visited[j][arr[j][i]] = true;
			while(q.size()){
				vector<int> v = q.front();
				
				// cout<<v[0]<<" "<<v[1]<<endl;
				if(v[0]!=0) break;
				cnt[j]--;
				q.pop();
				for(auto k: e[j][v[1]]){
					indeg[j][k]-=1;
					if(indeg[j][k] == 0 &&visited[j][k] && k!=0){
						q.push({0,k});
					}
				}
			}
		}
		//check if everyone if 0
		
		for(int j = 0;j<M;j++){
			// cout<<cnt[j]<<" ";
			if(cnt[j]) 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(3,1,{-1, 0, 0},{{1,2}});
// 	// cout<<solve(5,2,{-1, 0, 1, 2, 3},{{4,1,3,2},{4,3,2,1}});
	
	
// 	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