QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107886#1825. The King's GuardsBalintR#WA 2ms3600kbC++204.5kb2023-05-23 04:56:452023-05-23 04:56:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-23 04:56:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3600kb
  • [2023-05-23 04:56:45]
  • 提交

answer

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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}

const int MN = 305;
const int MV = MN*3;

namespace Flow {
    struct Edge {
        int node, rev, cap;
        bool real;
    };

    vector<Edge> adjList[MV];

    void addEdge(int a, int b, int c){
        adjList[a].pb({b, SZ(adjList[b]), c, true});
        adjList[b].pb({a, SZ(adjList[a])-1, 0, false});
    }

    void rmEdge(int a, int b){
        adjList[a].pop_back();
        adjList[b].pop_back();
    }

    void reset(){
        FR(i, MV) for(Edge &e : adjList[i]) if(!e.real) adjList[e.node][e.rev].cap += e.cap, e.cap = 0;
    }

    int ancFlow[MV], ePar[MV];
    int qu[MV], ql, qr;

    int bfs(int s, int t){
        ms(ePar, -1);
        ePar[s] = -2;
        ql = qr = 0;
        qu[qr++] = s;
        ancFlow[s] = INF;

        while(ql < qr){
            int n1 = qu[ql++];
            //dbg(n1);
            for(Edge e : adjList[n1]){
                int n2 = e.node;
                if(!e.cap || ePar[n2] != -1) continue;
                ancFlow[n2] = min(ancFlow[n1], e.cap);
                ePar[n2] = e.rev;
                qu[qr++] = e.node;
            }
        }

        if(ePar[t] == -1) return 0;

        int f = ancFlow[t];
        int n1 = t;
        while(n1 != s){
            Edge &e = adjList[n1][ePar[n1]];
            adjList[e.node][e.rev].cap -= f;
            e.cap += f;
            n1 = e.node;
        }

        return f;
    }

    int getFlow(int s, int t){
        //cerr << s << ' ' << t << endl;
        int res = 0;
        while(true){
            int f = bfs(s, t);
            //dbg(f);
            res += f;
            if(!f) break;
        }
        //dbg(res);
        return res;
    }
}

int n, m, g;
int dsu[MN];
pair<int, pii> allEdges[MN*MN];
vector<pair<int, pii>> edges;
bool inAns[MN];

int find(int a){
    return dsu[a] < 0 ? a : dsu[a] = find(dsu[a]);
}

void kruskal(){
    sort(allEdges, allEdges + m);
    ms(dsu, -1);
    FR(i, m){
        auto [c, p] = allEdges[i];
        auto [a, b] = p;
        a = find(a), b = find(b);
        if(a != b){
            dsu[b] = a;
            edges.pb(allEdges[i]);
        }
    }
}

bool check(){
    ms(dsu, -1);
    FR(i, SZ(edges)) if(inAns[i]){
        auto [a, b] = edges[i].sn;
        a = find(a), b = find(b);
        if(a != b) dsu[b] = a;
    }

    int numRoot = 0;
    FR(i, n) numRoot += dsu[i] < 0;

    FR(i, n) Flow::addEdge(n+i, n+n+find(i), 1);
    bool good = Flow::getFlow(MV-2, MV-1) == numRoot;
    Flow::reset();
    FR(i, n) Flow::rmEdge(n+i, n+n+find(i));
    return good;
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> g;
    FR(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        allEdges[i] = {c, {a, b}};
    }
    kruskal();
    //cerr << "a" << endl;

    FR(i, g){
        int k; cin >> k;
        FR(i, k){
            int a; cin >> a; a--;
            Flow::addEdge(i, n+a, 1);
        }
    }
    FR(i, n) Flow::addEdge(MV-2, i, 1);
    FR(i, n) Flow::addEdge(n+n+i, MV-1, 1);

    FR(i, n) Flow::addEdge(n+i, n+n+i, 1);
    if(Flow::getFlow(MV-2, MV-1) != g) return !printf("-1\n");
    Flow::reset();
    FR(i, n) Flow::rmEdge(n+i, n+n+i);

    int ans = 0;
    fill_n(inAns, SZ(edges), true);
    FORR(i, SZ(edges)-1, 0){
        inAns[i] = false;
        if(!check()) inAns[i] = true, ans += edges[i].fs;
    }
    cout << ans << '\n';
}

详细

Test #1:

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

input:

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4

output:

8

result:

ok answer is '8'

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3600kb

input:

10 19 6
1 5 761
6 8 606
3 9 648
2 4 115
5 8 814
1 2 712
4 10 13
5 10 797
3 4 956
1 7 73
5 7 192
2 7 110
5 9 302
3 6 120
6 9 494
1 3 668
3 7 966
6 10 974
3 8 41
2 10 5
3 6 4 3
2 1 7
2 10 8
3 10 7 8
2 2 1

output:

-1

result:

wrong answer expected '429', found '-1'