QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629637#9349. Exchanging GiftsyumingskWA 156ms55068kbC++142.4kb2024-10-11 14:00:222024-10-11 14:00:22

Judging History

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

  • [2024-10-11 14:00:22]
  • 评测
  • 测评结果:WA
  • 用时:156ms
  • 内存:55068kb
  • [2024-10-11 14:00:22]
  • 提交

answer

#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";

using namespace std;
const int Mod = 998244353;
using ll = long long;
vector<int> e[1000005];
vector<int> sq[1000000 + 1];
int deg[1000005];
map<int, int> ma;
vector<int> tp(1000005);
void bfs(int u)
{
    queue<int> q;
    q.push(u);
    tp[u] = 1;
    while (!q.empty())
    {

        int t = q.front();
        q.pop();
        // cout << t << '\n';
        for (auto v : e[t])
        {
            // cout << v << '\n';
            tp[v] += tp[t];
            deg[v]--;
            if (deg[v] == 0)
            {
                q.push(v);
            }
        }
    }

    return;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n + 1; i++)
        e[i].clear(), sq[i].clear(), tp[i] = 0, deg[i] = 0;
    ma.clear();
    for (int i = 1; i <= n; i++)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int len;
            cin >> len;
            sq[i].resize(len);
            for (int j = 1; j <= len; j++)
            {
                int x;
                cin >> x;
                sq[i][j - 1] = x;
            }
        }
        else
        {
            int x, y;
            cin >> x >> y;
            e[i].push_back(x);
            e[i].push_back(y);
            deg[x]++;
            deg[y]++;
        }
    }
    // cout << "SS\n";
    ll sum = 0;
    ll mx = 0;
    bfs(n);
    for (int i = 1; i <= n; i++)
    {
        if (!sq[i].empty() && tp[i] > 0)
        {
            for (auto v : sq[i])
                ma[v] += tp[i];
        }
    }
    for (auto v : ma)
    {
        sum += v.second;
        mx = max(mx, v.second * 1LL);
    }
    // cout << sum << " " << mx << '\n';
    if (mx > sum - mx)
    {
        cout << 2LL * (sum - mx) << '\n';
    }
    else
    {
        cout << sum << '\n';
    }
}
int main()
{
    IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
    clock_t start_time = clock();
#endif
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
#ifndef ONLINE_JUDGE
    cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 55068kb

input:

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

output:

4
6

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 156ms
memory: 54976kb

input:

10000
100
1 30 371028678 371028678 371028678 716418076 398221499 591504380 398221499 398221499 591504380 777141390 398221499 591504380 591504380 777141390 287847807 716418076 777141390 716418076 777141390 287847807 287847807 287847807 371028678 371028678 398221499 777141390 371028678 6827702 6827702...

output:

0
0
0
0
29
0
0
0
0
0
0
32
16
0
30
32
24
0
0
0
28
0
0
0
0
5
0
0
0
0
10
0
0
0
9
0
0
0
0
8
0
25
0
0
0
0
18
0
0
0
0
0
4
18
0
19
0
0
0
0
0
0
0
0
37
0
0
18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
2
23
0
0
0
20
0
0
23
0
12
0
0
0
0
0
0
0
10
0
0
0
0
0
35
0
0
25
0
0
0
0
22
0
0
0
0
0
0
12
0
0
0
0
94
0
23
0
0
0
0...

result:

wrong answer 1st lines differ - expected: '700', found: '0'