Submission #1085852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085852		veehj	September (APIO24_september)	C++17	0 / 100	1 ms	604 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
int n, m, ans; 
vector<int> f, deg;
vector<pair<int, int>> t;
vector<vector<int>> s;
set<int> can, curr, era;

void cut(int x){
	era.insert(x);
	can.erase(x);
	if(x==0) return;
	deg[f[x]]--;
	if(deg[f[x]]==0){
		if(curr.count(f[x])) cut(f[x]);
		else can.insert(f[x]);
	}
}

void go(int x){
	for(int i=t[x].F; i<=t[x].S; i++){
		curr.insert(s[0][i]);
	}
	while(sz(curr)){
		for(auto& u : curr){
			if(can.count(u) && !era.count(u)) cut(u);
		}
		while(!sz(era)){
			x++;
			ans--;
			for(int i=t[x].F; i<=t[x].S; i++){
				if(can.count(s[0][i])) cut(s[0][i]);
				else curr.insert(s[0][i]);
			}
		}
		for(auto& u : era) curr.erase(u);
		era={};
	}
	if(x!=sz(t)-1) return go(x+1);
}

int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
	deg.assign(n, 0);
	t={};
	can={};
	curr={};
	era={};
	map<int, pair<int, int>> mp;
	for(int i=0; i<n-1; i++){
		mp[s[0][i]].F=i;
		mp[s[0][i]].S=i;
	}
	for(int i=1; i<m; i++){
		for(int j=0; j<n-1; j++){
			mp[s[i][j]].F=min(mp[s[i][j]].F, j);
			mp[s[i][j]].S=max(mp[s[i][j]].S, j);
		}
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for(int i=1; i<n; i++){
		q.push({mp[i].F, mp[i].S});
	}
	int l=0, r=0;
	while(!q.empty()){
		pair<int, int> nw=q.top();
		q.pop();
		if(nw.F<=r){
			r=max(r, nw.S);
		} else {
			t.pb({l, r});
			l=nw.F;
			r=nw.S;
		}
	}
	t.pb({l, r});
	for(auto& u : f) if(u!=-1) deg[u]++;
	for(int i=0; i<n; i++){
		if(deg[i]==0) can.insert(i);
	}
	ans=t.size();
	go(0);
	return ans;
}

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