QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209844#7107. ChaleurPetroTarnavskyi#AC ✓756ms24072kbC++171.9kb2023-10-10 18:21:282023-10-10 18:21:28

Judging History

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

  • [2023-10-10 18:21:28]
  • 评测
  • 测评结果:AC
  • 用时:756ms
  • 内存:24072kb
  • [2023-10-10 18:21:28]
  • 提交

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 << 17;
VI g[N];

int solve(int a, int b, VI vals)
{
	VI startSZ = vals;
	int n = SZ(vals);
	
	set<pair<PII, int>> vali;
	FOR(i, 0, n)
		vali.insert(MP(MP(vals[i], startSZ[i]), i));
			
	VI used(n, 0);
	int all = 0;
	while(true)
	{
		if(vali.begin()->F.F == vali.rbegin()->F.F && vali.begin()->F.F + all == SZ(vali) - 1)
			break;
	
	
		int v = vali.begin()->S;	
		vali.erase(vali.begin());
		used[v] = 1;
		all += a;			
		for(int to : g[v])
		{
			if(used[to])
				continue;
				
			vali.erase(MP(MP(vals[to], startSZ[to]), to));
			vals[to] += b;
			vali.insert(MP(MP(vals[to], startSZ[to]), to));
		}		
	}
		
	VI cnt(n, 0);
	all = 0;
	for(auto [_, v] : vali)
	{
		all -= a;
		for(int to : g[v])
		{
			if(used[to] == 0)
				continue;
				
			cnt[to] -= b;
		}
	}
	
	
	
	int ans = 1;
	FOR(i, 0, n)
	{
		if(used[i] == 1 && cnt[i] + all == SZ(vali) - 1)
			ans++;
	}
	
	return ans;
}



void solve()
{
	int n, m;
	cin >> n >> m;
	FOR(i, 0, m)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	VI vals(n);
	FOR(i, 0, n)
		vals[i] = SZ(g[i]);
	cout << solve(0, -1, vals) << " "; 

	FOR(i, 0, n)
		vals[i] = n - 1 - SZ(g[i]);	
	cout << solve(-1, 1, vals) << "\n"; 
	
	
	FOR(i, 0, n)
		g[i].clear();
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int t;
	cin >> t;
	while(t--)
		solve();
	
	
	
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6672kb

input:

3
3 2
1 2
2 3
6 6
1 2
2 3
1 3
1 4
2 5
3 6
4 1
1 2

output:

2 1
1 4
1 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 756ms
memory: 24072kb

input:

2231
1 0
5 7
4 1
3 4
3 1
3 5
4 2
3 2
4 5
5 4
2 1
2 5
2 4
2 3
5 10
3 2
2 5
1 4
4 2
4 5
1 2
1 3
3 5
3 4
1 5
5 10
1 3
2 4
1 4
5 2
2 3
1 5
5 4
1 2
3 4
5 3
5 9
2 5
3 5
2 3
2 1
4 3
3 1
4 1
4 5
2 4
5 4
4 2
4 1
4 5
4 3
5 9
4 1
4 5
3 4
2 4
2 1
3 1
2 5
3 5
3 2
5 4
2 5
2 3
2 1
2 4
5 9
5 2
1 3
4 3
1 2
5 4
4 2
5...

output:

1 1
3 1
4 1
1 5
1 5
2 1
4 1
2 1
4 1
2 1
2 1
3 1
4 1
4 1
1 5
2 1
4 1
1 5
1 5
1 5
3 1
4 1
4 1
4 1
3 1
3 1
4 1
4 1
2 1
4 1
4 1
1 5
1 5
2 1
4 1
4 1
4 1
3 1
2 1
4 1
2 1
4 1
4 1
4 1
3 1
1 5
4 1
4 1
1 5
2 1
4 1
2 1
2 1
1 5
4 1
1 5
3 1
4 1
1 5
2 1
1 5
3 1
3 1
1 5
3 1
3 1
2 1
1 5
4 1
3 1
1 5
2 1
3 1
2 1
2 1
...

result:

ok 2231 lines

Extra Test:

score: 0
Extra Test Passed