QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629649#9349. Exchanging GiftsyumingskWA 211ms57336kbC++142.6kb2024-10-11 14:04:022024-10-11 14:04:08

Judging History

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

  • [2024-10-11 14:04:08]
  • 评测
  • 测评结果:WA
  • 用时:211ms
  • 内存:57336kb
  • [2024-10-11 14:04:02]
  • 提交

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);
int vis[1000005];
int n;
void bfs(int u)
{

    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (deg[i] == 0)
        {
            q.push(i);
            tp[i] = 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()
{
    cin >> n;
    for (int i = 1; i <= n + 1; i++)
        e[i].clear(), sq[i].clear(), tp[i] = 0, deg[i] = 0, vis[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: 3ms
memory: 57336kb

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: 211ms
memory: 56792kb

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:

18090
2925
3592
9484
4122
38173
13999
11540
7688
0
16274
14692
2367
6339
12336
17359
21134
14047
16406
9950
76807
16634
42204
25104
17568
15665
0
4243
20647
17785
9519
12748
11672
28620
7982
57812
51351
37296
26850
13645
22727
45442
11263
23359
0
10290
17900
4079
0
14518
19528
15748
12719
16920
6587...

result:

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