QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373458#2830. Data StructurePetroTarnavskyiWA 30ms7708kbC++204.6kb2024-04-01 18:02:192024-04-01 18:02:20

Judging History

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

  • [2024-04-01 18:02:20]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:7708kb
  • [2024-04-01 18:02:19]
  • 提交

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]] >= -1)
			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);
	for(int to : gr[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)
		{			
			component.clear();
			dfs(i);
			if(!solve(component))
			{
				bad();
				return;
			}

		}
	}	
	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] = cnt[to] + 1;
			if(!solve(component))
			{
				bad();
				return;
			}
		}
	}
	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] = cnt[to] + 1;
			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;
}

详细

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: 5888kb

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: 0
Accepted
time: 0ms
memory: 7708kb

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:

2
1 4
2 3
2
1 4
2 5
2
2 4
5 6
2
2 3
1 4
2
1 5
3 4
2
3 5
1 6
2
1 4
2 3
2
3 4
2 5
2
1 6
3 4
2
1 2
1 3
2
1 2
1 4
2
4 3
1 4
2
2 1
2 3
2
2 1
2 3
2
1 3
1 4
-1
3
2 1
3 1
2 3
3
2 1
4 1
2 4
-1
3
2 3
1 2
1 3
3
1 3
2 1
2 3
1
2 3
1
3 4
1
1 4
0
0
0

result:

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

Test #4:

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

input:

3 6
1 1
1 2
1 2
1 3
1 3
1 1
3 7
1 3
0
1 2
1 2
1 1
1 1
1 3
3 8
0
1 3
1 2
0
1 1
1 1
1 2
1 3
3 6
1 3
1 3
1 2
1 1
1 1
1 2
3 7
1 1
1 3
1 1
1 2
1 2
1 3
0
3 8
1 1
1 2
0
1 3
1 2
0
1 3
1 1
3 6
1 3
1 1
1 2
1 3
1 2
1 1
3 7
1 1
1 2
0
1 1
1 3
1 3
1 2
3 8
1 2
1 1
1 3
1 2
0
1 3
0
1 1
3 6
1 2
1 2
1 3
1 1
1 1
1 3
3 ...

output:

3
1 6
2 3
4 5
3
5 6
3 4
1 7
3
5 6
3 7
2 8
3
4 5
3 6
1 2
3
1 3
4 5
2 6
3
1 8
2 5
4 7
3
2 6
3 5
1 4
3
1 4
2 7
5 6
3
2 8
1 4
3 6
3
4 5
1 2
3 6
3
2 5
4 7
3 6
3
3 4
1 2
5 8
3
1 6
2 5
3 4
3
5 6
1 3
4 7
3
6 7
2 5
4 8
3
1 2
3 6
4 5
3
1 3
5 6
2 7
3
3 7
2 4
6 8
3
1 5
4 6
2 3
3
4 7
1 5
2 3
3
1 6
5 7
4 8
3
4 6
...

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

score: 0
Accepted
time: 5ms
memory: 5904kb

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

4
4 6
5 8
1 2
3 7
4
4 6
3 8
1 9
5 7
4
1 7
4 5
2 3
8 9
4
5 7
3 4
2 8
1 6
4
3 7
6 8
2 4
1 5
4
2 8
3 7
4 9
1 10
4
7 8
1 5
3 6
2 4
4
1 9
4 6
3 5
2 8
4
4 7
2 3
8 10
5 6
4
1 3
4 7
2 8
5 6
4
2 9
1 7
5 6
3 4
4
2 10
1 9
4 5
3 8
4
2 5
1 3
4 8
6 7
4
1 5
3 8
4 9
2 7
4
3 6
2 9
5 7
1 8
4
2 8
6 7
1 5
3 4
4
2 8
6 7...

result:

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

Test #6:

score: -100
Wrong Answer
time: 30ms
memory: 5680kb

input:

5 10
1 1
1 4
1 2
1 4
1 5
1 2
1 3
1 5
1 1
1 3
5 11
1 1
1 3
1 1
1 2
1 5
1 2
0
1 5
1 4
1 3
1 4
5 12
1 2
0
1 1
1 5
1 2
1 4
1 3
1 4
0
1 5
1 3
1 1
5 10
1 3
1 5
1 1
1 1
1 2
1 4
1 4
1 5
1 2
1 3
5 11
1 3
1 5
1 2
1 2
1 4
1 3
1 1
1 1
0
1 4
1 5
5 12
1 3
1 4
1 2
0
1 5
1 1
1 2
1 1
1 4
1 5
0
1 3
5 10
1 4
1 5
1 3
1...

output:

5
1 9
3 6
7 10
2 4
5 8
5
1 3
4 6
2 10
9 11
5 8
5
3 12
1 5
7 11
6 8
4 10
5
3 4
5 9
1 10
6 7
2 8
5
7 8
3 4
1 6
5 10
2 11
5
6 8
3 7
1 12
2 9
5 10
5
4 7
8 9
3 10
1 5
2 6
5
2 4
1 6
5 7
8 9
3 11
5
1 7
2 3
10 11
8 9
4 5
5
8 10
4 5
6 7
2 9
1 3
5
6 7
1 11
4 5
2 3
8 9
5
2 6
4 11
8 9
1 7
3 10
5
7 8
1 10
4 5
3 ...

result:

wrong answer Should find solution [Case 6652]