QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209844 | #7107. Chaleur | PetroTarnavskyi# | AC ✓ | 756ms | 24072kb | C++17 | 1.9kb | 2023-10-10 18:21:28 | 2023-10-10 18:21:28 |
Judging History
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