QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#437218#8131. Filesystemucup-team3215WA 1ms3876kbC++233.5kb2024-06-09 06:45:592024-06-09 06:45:59

Judging History

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

  • [2024-06-09 06:45:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3876kb
  • [2024-06-09 06:45:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll INF = 1e9 + 7;

struct Dinic {

    struct edge {
        ll from, to;
        ll cap, flow;
    };
    ll n;

    vector<vector<ll>> g;
    vector<edge> E;

    Dinic(ll n) : n(n) {
        g.resize(n);
    }

    void addEdge(ll from, ll to, ll cap) {
        g[from].push_back(E.size());
        E.push_back({from, to, cap, 0});
        g[to].push_back(E.size());
        E.push_back({to, from, 0, 0});
    }

    vector<ll> bfs(ll st, ll mn) {
        ll n = g.size();
        vector<ll> d(n, -1);
        d[st] = 0;
        queue<ll> q;
        q.push(st);
        while (!q.empty()) {
            ll v = q.front();
            q.pop();
            for (const auto ind: g[v]) {
                ll to = E[ind].to;
                if (d[to] == -1 && E[ind].cap - E[ind].flow >= mn) {
                    d[to] = d[v] + 1;
                    q.push(to);
                }
            }
        }

        return d;
    }

    ll solve(ll st, ll en) {
        ll res = 0;
        for (ll i = 29; i >= 0; --i) {
            while (1) {
                vector<ll> d = bfs(st, (1ll << i));
                if (d[en] == -1)break;
                vector<ll> ptr(g.size(), 0);
                while (ll add = dfs(st, INF, (1ll << i), en, d, ptr)) {
                    res += add;
                }
            }
        }
        return res;
    }

    ll dfs(ll v, ll flow, const ll mn, const ll end, const vector<ll> &d, vector<ll> &ptr) {
        if (flow < mn) {
            return 0;
        }
        if (v == end) {
            return flow;
        }
        for (; ptr[v] < g[v].size(); ++ptr[v]) {
            ll ind = g[v][ptr[v]];
            ll to = E[ind].to;
            if (d[to] != d[v] + 1)continue;
            if (ll add = dfs(to, min(flow, E[ind].cap - E[ind].flow), mn, end, d, ptr)) {
                E[ind].flow += add;
                E[ind ^ 1].flow -= add;
                return add;
            }
        }
        return 0;
    }
};

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<char> need(n, 0);
    for (ll i = 0; i < k; ++i) {
        ll x;
        cin >> x;
        --x;
        need[x] = 1;
    }
    ll st = 0, en = n + 1;
    Dinic sol(en + 1);
    vector<ll> p(n);
    for (auto &i: p) {
        cin >> i, --i;
    }
    for (ll i = 0; i < n; ++i) {
        sol.addEdge(st, i + 1, 0);
        sol.addEdge(i + 1, st, 0);
        sol.addEdge(en, i + 1, 0);
        sol.addEdge(i + 1, en, 0);
    }
    for (ll i = 0; i < n; ++i) {
        if (need[i]) {
            ll nxt = i + 1 < n && need[i + 1] ? i + 1 : -1;
            if (~nxt) {
                sol.addEdge(i + 1, nxt + 1, 1);
                sol.addEdge(nxt + 1, i + 1, 1);
            } else {
                sol.addEdge(i + 1, en, 1);
                sol.addEdge(en, i + 1, 1);
            }
        }
    }
    for (ll j = 0; j < n; ++j) {
        ll i = p[j];
        if (need[i]) {
            ll nxt = j + 1 < n && need[p[j + 1]] ? p[j + 1] : -1;
            if (~nxt) {
                sol.addEdge(i + 1, nxt + 1, 1);
                sol.addEdge(nxt + 1, i + 1, 1);
            } else {
                sol.addEdge(i + 1, st, 1);
                sol.addEdge(st, i + 1, 1);
            }
        }
    }
    cout << sol.solve(st,en) << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)solve();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

2
12 8
2 5 8 3 4 10 12 1
10 5 8 6 4 7 2 3 11 12 1 9
8 4
1 3 5 7
1 4 5 8 7 6 3 2

output:

3
4

result:

ok 2 number(s): "3 4"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

100
10 3
10 5 2
2 4 9 8 7 3 1 5 10 6
10 3
8 1 10
8 4 3 7 1 2 9 5 6 10
10 3
6 5 2
8 7 6 4 2 10 1 3 5 9
10 3
5 8 4
10 4 5 7 8 9 1 2 3 6
10 3
8 4 10
10 6 9 2 8 7 1 4 3 5
10 3
9 8 1
8 5 6 10 2 4 1 7 9 3
10 3
5 4 1
7 5 8 4 3 6 9 10 2 1
10 3
2 4 3
6 7 3 9 1 2 5 8 4 10
10 3
9 5 3
6 10 7 4 9 3 1 8 5 2
10 3
...

output:

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

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

100
10 5
2 6 1 9 3
10 8 2 6 9 7 5 1 3 4
10 5
7 10 1 3 6
5 7 3 9 4 1 8 2 10 6
10 5
8 3 6 2 9
4 2 9 3 8 1 6 10 7 5
10 5
5 6 7 4 3
3 7 6 2 1 5 9 8 10 4
10 5
1 6 8 10 5
8 6 3 10 1 4 7 9 5 2
10 5
6 5 1 3 9
8 10 5 3 6 1 9 2 7 4
10 5
8 6 2 7 1
3 6 5 10 9 1 2 7 4 8
10 5
6 10 8 4 2
3 9 7 5 4 1 10 6 2 8
10 5
...

output:

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

result:

ok 100 numbers

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3660kb

input:

100
10 8
3 4 9 1 8 7 2 10
9 1 7 10 5 6 2 4 8 3
10 8
9 1 8 4 2 10 3 7
4 9 8 3 7 10 2 1 5 6
10 8
4 8 3 6 9 10 7 1
10 3 5 1 6 4 8 9 2 7
10 8
2 4 5 9 7 3 10 8
10 7 2 9 3 4 8 6 1 5
10 8
3 1 8 5 9 2 10 6
10 9 2 7 1 8 3 5 4 6
10 8
10 9 3 5 6 4 7 2
1 10 2 4 7 5 8 3 9 6
10 8
7 1 8 9 2 10 5 4
2 4 10 3 6 1 8 7...

output:

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

result:

wrong answer 78th numbers differ - expected: '2', found: '3'