QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130970#4938. Writing TaskskarunaTL 5ms19356kbC++174.1kb2023-07-25 22:30:002023-07-25 22:30:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-25 22:30:01]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:19356kb
  • [2023-07-25 22:30:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 202020;
int n, src, snk, N1, N2, N3;
vector<int> G[3][3][MAXN / 4];
set<pair<int, int>> S1, S2, S3;
map<array<int, 3>, int> mp;

int f(int x, int y, int z) {
    if (mp.find({x, y, z}) == mp.end()) {
        mp[{x, y, z}] = 1 + mp.size();
    }
    return mp[{x, y, z}];
}

vector<int> gph[MAXN];
vector<int> vec;
int vis[MAXN];

void dfs(int v) {
    if (vis[v]) return;
    vis[v] = 1;
    vec.push_back(v);
    for (int x : gph[v]) dfs(x);
}

int dp[2][MAXN];
void solve(int p, int v) {
    for (int x : gph[v]) if (p != x) {
        solve(v, x);
        dp[0][v] += max(dp[1][x], dp[0][x]);
        dp[1][v] += dp[0][x];
    }
    dp[1][v]++;
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> N1 >> N2 >> N3;
    for (int i = 1; i <= N1; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            int x; cin >> x;
            S1.insert({i, x});
            G[0][1][i].push_back(x);
            G[1][0][x].push_back(i);
        }
    }
    for (int i = 1; i <= N1; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            int x; cin >> x;
            S2.insert({i, x});
            G[0][2][i].push_back(x);
            G[2][0][x].push_back(i);
        }
    }
    for (int i = 1; i <= N2; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            int x; cin >> x;
            S3.insert({i, x});
            G[1][2][i].push_back(x);
            G[2][1][x].push_back(i);
        }
    }
    set<pair<int, int>> st;
    for (auto [x, y] : S1) {
        vector<int> v;
        for (int z : G[0][2][x]) for (int z1 : G[1][2][y]) {
            if (z == z1) v.push_back(f(x, y, z));
        }
        for (int i = 0; i < (int)v.size() - 1; i++) {
            int u1 = v[i];
            int u2 = v[i + 1];
            gph[u1].push_back(u2);
            gph[u2].push_back(u1);
            st.insert({u1, u2});
            st.insert({u2, u1});
        }
    }
    for (auto [x, z] : S2) {
        vector<int> v;
        for (int y : G[0][1][x]) for (int y1 : G[2][1][z]) {
            if (y == y1) v.push_back(f(x, y, z));
        }
        for (int i = 0; i < (int)v.size() - 1; i++) {
            int u1 = v[i];
            int u2 = v[i + 1];
            gph[u1].push_back(u2);
            gph[u2].push_back(u1);
            st.insert({u1, u2});
            st.insert({u2, u1});
        }
    }
    for (auto [y, z] : S3) {
        vector<int> v;
        for (int x : G[1][0][y]) for (int x1 : G[2][0][z]) {
            if (x == x1) v.push_back(f(x, y, z));
        }
        for (int i = 0; i < (int)v.size() - 1; i++) {
            int u1 = v[i];
            int u2 = v[i + 1];
            gph[u1].push_back(u2);
            gph[u2].push_back(u1);
            st.insert({u1, u2});
            st.insert({u2, u1});
        }
    }
    n = mp.size();
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        dfs(i);

        bool flag = false;
        for (int x : vec) 
            if (gph[x].size() == 3) flag = true;

        if (flag) {
            assert(vec.size() <= 8);
            int sz = vec.size();
            int cnt = 0;
            for (int j = 0; j < (1 << sz); j++) {
                bool flag = true;
                for (int u = 0; u < sz; u++) if (j >> u & 1) {
                    for (int v = 0; v < sz; v++) if (j >> v & 1) 
                        if (st.find({vec[u], vec[v]}) != st.end()) flag = false;
                }
                if (flag) cnt = max(cnt, __builtin_popcount(j));
            }
            ans += cnt;
        }
        else {
            bool flag = false;
            for (int x : vec) 
                if (gph[x].size() == 1) flag = true;
            
            if (flag) {
                solve(vec[0], vec[0]);
                ans += max(dp[0][vec[0]], dp[1][vec[0]]);
            }
            else
                ans += (int)vec.size() / 2;
        }
        vec.clear();
    }
    cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 19012kb

input:

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

output:

2

result:

ok single line: '2'

Test #2:

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

input:

2 2 2
0
1 2
0
2 1 2
2 1 2
0

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Time Limit Exceeded

input:

40623 39265 42226
2 14643 37432
2 29610 20181
2 6441 7614
2 17559 3238
2 39001 17644
2 6431 37097
2 6347 12246
2 1130 1688
2 38583 9078
2 8746 27832
2 13090 39048
2 32647 18777
2 27505 19277
2 31201 25824
2 6133 20344
2 11625 20997
2 18528 35730
0
2 22986 5273
2 10942 38791
2 19025 35679
2 32321 124...

output:


result: