QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#626039	#6315. 填数游戏	propane	100 ✓	1674ms	161560kb	C++20	6.3kb	2024-10-09 22:35:49	2024-10-09 22:35:52

Judging History

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

[2024-10-09 22:35:52]
评测

测评结果：100
用时：1674ms
内存：161560kb

查看

[2024-10-09 22:35:49]
提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 1e6 + 5;
int p[maxn], sz1[maxn], sz2[maxn];

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    if (x == y){
        sz2[x] += 1;
    }
    else{
        p[x] = y;
        sz1[y] += sz1[x];
        sz2[y] += sz2[x] + 1; 
    }
}

vector<pair<int, int> > g[maxn];

int tr[maxn * 4], tag[maxn * 4];

void clear(int n){
    for(int i = 1; i <= 4 * n; i++){
        tr[i] = tag[i] = 0;
    }
}

void update(int u, int x){
    tr[u] += x;
    tag[u] += x;
}

void pushdown(int u){
    update(2 * u, tag[u]);
    update(2 * u + 1, tag[u]);
    tag[u] = 0;
}

void modify(int u, int l, int r, int L, int R, int v){
    if (l > R or r < L) return;
    if (l >= L and r <= R){
        update(u, v);
        return;
    }
    pushdown(u);
    int mid = (l + r) / 2;
    modify(2 * u, l, mid, L, R, v);
    modify(2 * u + 1, mid + 1, r, L, R, v);
    tr[u] = min(tr[2 * u], tr[2 * u + 1]);
}

pair<int, int> p1[maxn], p2[maxn];

int in[maxn], out[maxn], ts;

void dfs1(int u, int fa, int len){
    in[u] = ++ts;
    for(auto [j, id] : g[u]){
        if (j == fa) continue;
        dfs1(j, u, len);
        auto [a, b] = p2[id];
        if (minmax(a, b) == minmax(u, j)){
            modify(1, 1, len, 1, in[j] - 1, 1);
            modify(1, 1, len, out[j] + 1, len, 1);
        }
        else{
            if (a == u or b == u){
                modify(1, 1, len, in[j], out[j], 1);
            }
            else if (a == j or b == j){
                modify(1, 1, len, 1, in[j] - 1, 1);
                modify(1, 1, len, out[j] + 1, len, 1);
            }
        }
    }
    out[u] = ts;
}

int dfs2(int u, int fa, int len){
    int ans = tr[1];
    for(auto [j, id] : g[u]){
        if (j == fa) continue;
        auto [a, b] = p2[id];
        if (minmax(a, b) == minmax(u, j)){
            modify(1, 1, len, 1, in[j] - 1, -1);
            modify(1, 1, len, out[j] + 1, len, -1);
            modify(1, 1, len, in[j], out[j], 1);
        }
        ans = max(ans, dfs2(j, u, len));
        if (minmax(a, b) == minmax(u, j)){
            modify(1, 1, len, 1, in[j] - 1, 1);
            modify(1, 1, len, out[j] + 1, len, 1);
            modify(1, 1, len, in[j], out[j], -1);
        }
    }
    return ans;
}

int solve_tree(int x){
    clear(sz1[x]);
    ts = 0;
    dfs1(x, -1, sz1[x]);
    return dfs2(x, -1, sz1[x]);
}

bool v[maxn], ins[maxn], oncycle[maxn];
int fa[maxn], fid[maxn];
vector<int> cycle, ids;

void dfs_cycle(int u, int from){
    v[u] = true;
    ins[u] = true;
    for(auto [j, id] : g[u]){
        if (id == from) continue;
        if (!v[j]){
            fa[j] = u;
            fid[j] = id;
            dfs_cycle(j, id);
        }
        else if (ins[j]){
            cycle.clear();
            ids.clear();
            int t = u;
            while(t != j){
                cycle.push_back(t);
                ids.push_back(fid[t]);
                t = fa[t];
            }
            cycle.push_back(j);
            ids.push_back(id);
        }
    }
    ins[u] = false;
}

int dfs3(int u, int fa){
    int ans = 0;
    for(auto [j, id] : g[u]){
        if (j == fa or oncycle[j]) continue;
        auto [a, b] = p2[id];
        if (a == j or b == j) ans += 1;
        ans += dfs3(j, u);
    }
    return ans;
}

int solve_cycle(int x){
    dfs_cycle(x, -1);
    for(auto u : cycle) oncycle[u] = true;
    int ans = 0;
    for(auto u : cycle){
        ans += dfs3(u, -1);
    }
    int cnt = 0;
    int t[2]{};
    for(int i = 0; i < ids.size(); i++){
        int a1 = cycle[i];
        int b1 = cycle[(i + 1) % ids.size()];
        auto [a2, b2] = p2[ids[i]];
        // 环长为1
        if (a1 == b1){
            return ans + (a2 == a1 or b2 == a1);
        }
        if (minmax(a1, b1) == minmax(a2, b2)) cnt += 1;
        else if (a2 == a1 or b2 == a1) {
            t[0] += 1;
        }
        else if (a2 == b1 or b2 == b1){
            t[1] += 1;
        }
    }
    if (t[0] > t[1]) swap(t[0], t[1]);
    if (t[0] + cnt < t[1]) ans += t[0] + cnt;
    else ans += (t[0] + t[1] + cnt) / 2;
    return ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif      

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= m; i++){
            p[i] = i;
            sz1[i] = 1;
            sz2[i] = 0;
            g[i].clear();
            v[i] = false;
            ins[i] = false;
            oncycle[i] = false;
            fa[i] = 0;
            fid[i] = 0;
        }
        for(int i = 0; i < n; i++){
            int c;
            cin >> c;
            int a, b;
            if (c == 1){
                cin >> a;
                b = a;
            }
            else{
                cin >> a >> b;
            }
            if (a > b) swap(a, b);
            p2[i] = {a, b};
        }
        for(int i = 0; i < n; i++){
            int c;
            cin >> c;
            int a, b;
            if (c == 1){
                cin >> a;
                b = a;
            }
            else{
                cin >> a >> b;
            }
            if (a > b) swap(a, b);
            merge(a, b);
            p1[i] = {a, b};
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        bool ok = true;
        for(int i = 1; i <= m; i++){
            if (find(i) == i){
                if (sz2[i] > sz1[i]){
                    ok = false;
                    break;
                }
            }
        }
        if (!ok){
            cout << -1 << '\n';
            continue;
        }
        int ans = 0;
        for(int i = 1; i <= m; i++){
            if (find(i) == i){
                if (sz1[i] == sz2[i] + 1){
                    ans += solve_tree(i);
                }
                else{
                    ans += solve_cycle(i);
                }
            }
        }
        cout << ans << '\n';
    }

}

源文件, 语言: C++20

詳細信息

Pretests

Final Tests

Test #1:

score: 4

Accepted

time: 0ms

memory: 22152kb

input:

output:

result:

ok 20 numbers

Test #2:

score: 4

Accepted

time: 2ms

memory: 3704kb

input:

output:

result:

ok 20 numbers

Test #3:

score: 4

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok 20 numbers

Test #4:

score: 4

Accepted

time: 1ms

memory: 3716kb

input:

output:

result:

ok 20 numbers

Test #5:

score: 4

Accepted

time: 0ms

memory: 3768kb

input:

output:

result:

ok 20 numbers

Test #6:

score: 4

Accepted

time: 4ms

memory: 3744kb

input:

output:

-1
-1
-1
-1
-1
-1
0
0
0
-1
-1
0
-1
0
0
0
0
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
0
0
-1
-1
-1
0
0
0
-1
-1
-1
0
0
0
-1
0
-1
0
0
0
0
0
0
-1
0
-1
0
0
-1
-1
0
0
-1
0
0
-1
0
0
0
-1
0
-1
0
0
-1
-1
-1
0
0
0
0
-1
-1
0
-1
-1
-1
-1
0
0
0
-1
0
0
-1
-1
-1
-1
0
-1
0
-1
0
0
0
0
-1
0
0
-1
0
0
0
-1
-1
0
0
-1
...

result:

ok 1000 numbers

Test #7:

score: 4

Accepted

time: 4ms

memory: 3740kb

input:

output:

result:

ok 1000 numbers

Test #8:

score: 4

Accepted

time: 3ms

memory: 3728kb

input:

output:

result:

ok 1000 numbers

Test #9:

score: 4

Accepted

time: 4ms

memory: 3728kb

input:

output:

result:

ok 1000 numbers

Test #10:

score: 4

Accepted

time: 3ms

memory: 3736kb

input:

output:

result:

ok 1000 numbers

Test #11:

score: 4

Accepted

time: 3ms

memory: 3668kb

input:

output:

result:

ok 1000 numbers

Test #12:

score: 4

Accepted

time: 42ms

memory: 4048kb

input:

output:

result:

ok 1000 numbers

Test #13:

score: 4

Accepted

time: 57ms

memory: 3980kb

input:

output:

result:

ok 1000 numbers

Test #14:

score: 4

Accepted

time: 150ms

memory: 55976kb

input:

output:

-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
0
0
0
-1
0
0
-1
-1
-1
-1
-1
-1
0
0
0
0
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
0
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
-1
0
0
-1
-1
-1
-1
-1
0
-1
-1
0
0
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-...

result:

ok 1000 numbers

Test #15:

score: 4

Accepted

time: 84ms

memory: 66824kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 4

Accepted

time: 74ms

memory: 54872kb

input:

output:

result:

ok 1000 numbers

Test #17:

score: 4

Accepted

time: 190ms

memory: 45984kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 4

Accepted

time: 185ms

memory: 50696kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 4

Accepted

time: 193ms

memory: 39568kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 4

Accepted

time: 188ms

memory: 49424kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 4

Accepted

time: 182ms

memory: 51268kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 4

Accepted

time: 183ms

memory: 49684kb

input:

output:

result:

ok 1000 numbers

Test #23:

score: 4

Accepted

time: 1657ms

memory: 153964kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 4

Accepted

time: 1657ms

memory: 161560kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 4

Accepted

time: 1674ms

memory: 158428kb

input:

output:

result:

ok 1000 numbers

Extra Test:

score: 0

Extra Test Passed