QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373449#2830. Data StructurePetroTarnavskyiRE 2ms7608kbC++204.5kb2024-04-01 17:48:582024-04-01 17:48:59

Judging History

你现在查看的是最新测评结果

  • [2024-04-01 17:48:59]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:7608kb
  • [2024-04-01 17:48:58]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 18;

int n, m;

vector<PII> ans;
VI cols[N];
set<int> freeCols;
VI where[N];

int whereUp(int v)
{
	for(int col : where[v])
	{
		assert(SZ(cols[col]) != 0);
		if(cols[col].back() == v)
			return col;
		assert(cols[col][0] == v);
	}
	assert(0);
}
void delCol(int v, int col)
{
	int id = -1;
	FOR(i, 0, SZ(where[v]))
		if(where[v][i] == col)
			id = i;
	assert(id != -1);
	where[v] = {where[v][id ^ 1]};
}

void move(int from, int to)
{
	assert(from != to);
	ans.PB(MP(from, to));
	
	if(SZ(cols[to]) == 0)
		freeCols.erase(to);
	if(SZ(cols[from]) == 1)
		freeCols.insert(from);
	
	
	int v = cols[from].back();

	cols[from].pop_back();
	cols[to].PB(v);
	
	delCol(v, from);
	where[v].PB(to);	
}
bool solve(int v)
{
	//cout << v << " " << where[v][0] << " " << where[v][1] << "\n";
	//in one col
	if(where[v][0] == where[v][1])
		return 1;
		
	//cerr << v << "\n";
	for(int col : where[v])
		assert(cols[col].back() == v);
	
	int id = -1;
	FOR(i, 0, 2)
	{
		if(SZ(cols[where[v][i]]) == 1)
			id = i;
	}
	if(id == -1)
	{
		if(SZ(freeCols) == 0)
			return 0;
		int to = *freeCols.begin();
		int fr0 = where[v][0];
		int fr1 = where[v][1];
		move(fr0, to);
		move(fr1, to);
	}
	else
		move(where[v][id ^ 1], where[v][id]);
	
	return 1;
}
int cnt[N];
bool solve(VI vs)
{
	if(SZ(vs) == 1)
		return solve(vs[0]);
	//FOR(i, 0, SZ(vs))
	//	cerr << vs[i] << " ";
	//cerr << "\n";
	//FOR(i, 0, SZ(vs))
	//	cerr << cnt[vs[i]] << " ";
	//cerr << "\n";
	
	FOR(i, 0, SZ(vs))
	{
		int j = i;
		while(j < SZ(vs) && cnt[vs[j]] <= 0)
			j++;
		assert(j != SZ(vs));
		
		RFOR(it, j + 1, i)
		{
			if(!solve(vs[it]))
				return 0;
		}
			
		i = j;
		while(j < SZ(vs) && cnt[vs[j]] >= 0)
			j++;
		
		FOR(it, i + 1, j)
		{
			if(!solve(vs[it]))
				return 0;
		}
		i = j - 1;
	}
	return 1;
}



VI component;
VI g[N], gr[N];
bool used[N];
void dfs(int v)
{
	used[v] = 1;
	component.PB(v);
	for(int to : g[v])
		if(!used[to])
			dfs(to);
}


void clear()
{
	FOR(i, 0, n)
	{
		g[i].clear();
		gr[i].clear();
		cnt[i] = used[i] = 0;
		
		where[i].clear();
		cols[i].clear();
	}
	component.clear();
	ans.clear();
	freeCols.clear();
}
void bad()
{
	cout << "-1\n";
	clear();
}

void solve()
{
	FOR(i, 0, m)
	{
		if(SZ(cols[i]) != 2)
			continue;
		int solvedFirst = cols[i][1];
		int solvedSecond = cols[i][0];
		
		if(solvedFirst == solvedSecond)
			continue;
		
		cnt[solvedFirst]++;
		cnt[solvedSecond]--;
		
		g[solvedFirst].PB(solvedSecond);
		gr[solvedSecond].PB(solvedFirst);
	}
	FOR(i, 0, n)
	{
		if(SZ(g[i]) + SZ(gr[i]) == 0)
		{
			solve(i);
			used[i] = 1;
		}
	}
	FOR(i, 0, n)
	{
		if(!used[i] && SZ(g[i]) + SZ(gr[i]) == 1)
		{
			if(SZ(freeCols) == 0)
			{
				bad();
				return;
			}
			component.clear();
			dfs(i);
			solve(component);
		}
	}	
	FOR(i, 0, n)
	{
		if(!used[i] && cnt[i] > 0)
		{
			component.clear();
			dfs(i);
			
			assert(component[0] == i);
			component.erase(component.begin());
			if(!solve(i))
			{
				bad();
				return;
			}
			
			for(int to : g[i])
				cnt[to] = max(0, cnt[to] + 1);
			solve(component);
		}
	}
	FOR(i, 0, n)
	{
		if(!used[i])
		{
			assert(cnt[i] == 0);
			
			component.clear();
			dfs(i);
			
			if(SZ(freeCols) == 0)
			{
				bad();
				return;
			}
			
			assert(component[0] == i);
			component.erase(component.begin());
			component.PB(i);
			
			move(whereUp(i), *freeCols.begin());
			
			cnt[i]--;
			for(int to : g[i])
				cnt[to]++;
			if(!solve(component))
			{
				bad();
				return;
			}
		}
	}
	
	cout << SZ(ans) << "\n";
	for(auto [from, to] : ans)
	{
		cout << from + 1 << " " << to + 1 << "\n";
	}
	clear();
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	while(cin >> n >> m)
	{
		FOR(i, 0, m)
		{
			int k;
			cin >> k;
			VI a(k);
			FOR(j, 0, k)
			{
				cin >> a[j];
				a[j]--;
				where[a[j]].PB(i);
			}
			if(k == 0)
				freeCols.insert(i);
			
			cols[i] = a;
		}
		solve();
	}
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5912kb

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
1 3
2 3
1 2
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 2ms
memory: 7608kb

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:

1
1 2
1
1 3
1
1 2
0
0
0

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

score: -100
Runtime Error

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:


result: