[Codeforces] 731D. 80-th Level Archeology

題目連結:http://codeforces.com/problemset/problem/731/D
我覺得我的作法感覺不太對(?但還是講一下好了
我的做法是先把大小關係建成一張DAG,而這樣的話會發現題目變成說可不可以找到一種拓樸排序方法使得序列會是循環的字串,而又已經知道循環其實就只有可能中間斷開一個而已,所以我們不妨找到中間斷開的那個關係,並追本朔源到最前面的那個,從他開始拓樸排序,看會不會是好的。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define FF first
#define SS second
const int N = 500000 + 5;
const int C = 1000000 + 5;

class DJS{
	private:
		vector<int> arr;
	public:
		inline void init(int n){
			arr.resize(n);
			for(int i=0;i<n;i++) arr[i]=i;
		}
		int query(int x){
			if(arr[x]!=x) arr[x] = query(arr[x]);
			return arr[x];
		}
		void merge(int a, int b){
			int u = query(a), v = query(b);
			arr[max(u, v)]=min(u, v);
		}
} djs;

vector<int> G[C], cur;
int in[C];

inline void kill(){cout<<"-1\n";exit(0);}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, c; cin>>n>>c;
	djs.init(c+1);
	int sz; cin>>sz;
	for(int j=0;j<sz;j++){
		int x; cin>>x;
		cur.PB(x);
	}
	int ll = c+1;
	for(int i=1;i<n;i++){
		bool flag = 1;
		cin>>sz;
		vector<int> tmp;
		for(int j=0;j<sz;j++){
			int x; cin>>x;
			tmp.PB(x);
			if(j >= (int)cur.size()) flag = 0;
			if(!flag) continue;
			if(tmp[j] != cur[j]){
				flag = 0;
				if(tmp[j] < cur[j]) ll = cur[j];
				else djs.merge(cur[j], tmp[j]);
				G[cur[j]].PB(tmp[j]);
				in[tmp[j]]++;
			}
		}
		if(flag and sz<(int)cur.size()) kill();
		cur = tmp;
	}
	if(ll==c+1) ll = 1;
	ll=djs.query(ll);
	for(int i=ll;i<=c;i++){
		if(in[i]!=0) kill();
		for(auto u: G[i]){
			if(in[u]==0) continue;
			in[u]--;
		}
	}
	for(int i=1;i<ll;i++){
		if(in[i]!=0) kill();
		for(auto u: G[i]){
			if(in[u]==0) continue;
			in[u]--;
		}
	}
	cout<<(1-ll+c)%c<<'\n';
	return 0;
}

留言

  1. 我是把滿足相鄰兩個元素會是照順序排的x畫成線段,再找一個被n - 1個線段覆蓋過得點就好了

    回覆刪除

張貼留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題