QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107892#1825. The King's GuardsBalintRRE 2ms3484kbC++205.2kb2023-05-23 05:32:482023-05-23 05:32:53

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 05:32:53]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3484kb
  • [2023-05-23 05:32:48]
  • 提交

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;}

template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){
    return os << "(" << p.fs << ", " << p.sn << ")";
}

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

template <typename T, int MSZ>
struct Dinic {
    const T TINF = INF;
    struct Edge {
        int node, rev;
        T cap;
        bool real;
    };

    int s, t;
    vector<Edge> adjList[MSZ];
    int dist[MSZ];
    int nxt[MSZ];

    void addEdge(int a, int b, T 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, MSZ) for(Edge &e : adjList[i]) if(!e.real) adjList[e.node][e.rev].cap += e.cap, e.cap = 0;
    }

    T dfs(int n1, T f){
        if(f == 0 || n1 == t) return f;
        T pushed = 0;
        while(nxt[n1] < SZ(adjList[n1])){
            Edge &e = adjList[n1][nxt[n1]];
            int n2 = e.node;
            if(dist[n1] < dist[n2]){
                T nf = dfs(n2, min(f, e.cap));
                e.cap -= nf;
                adjList[n2][e.rev].cap += nf;
                pushed += nf;
                f -= nf;
                if(f == 0) break;
            }
            nxt[n1]++;
        }
        return pushed;
    }

    T maxFlow(int inS, int inT){
        s = inS; t = inT;
        T f = 0;
        while(true){
            ms(nxt, 0);
            ms(dist, -1);
            dist[s] = 0;
            queue<int> qu;
            qu.push(s);

            while(!qu.empty()){
                int n1 = qu.front(); qu.pop();
                if(n1 == t) break;
                for(Edge e : adjList[n1]){
                    int n2 = e.node;
                    if(e.cap == 0 || dist[n2] != -1) continue;
                    dist[n2] = dist[n1] + 1;
                    qu.push(n2);
                }
            }

            if(dist[t] == -1) return f;
            f += dfs(s, TINF);
        }
    }
};

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

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

void kruskal(){
    sort(allEdges, allEdges + m);

    edges = vector<pair<int, pii>>(allEdges, allEdges + m);
    return;

    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) dinic.addEdge(n+i, n+n+find(i), 1);
    int f = dinic.maxFlow(MV-2, MV-1);
    dinic.reset();
    FR(i, n) dinic.rmEdge(n+i, n+n+find(i));

    //dbgArr(inAns, SZ(edges));
    //cerr << f << ' ' << numRoot << endl;

    //assert(f <= numRoot);
    return f == numRoot;
}

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(j, k){
            int a; cin >> a; a--;
            dinic.addEdge(i, n+a, 1);
        }
    }
    FR(i, g) dinic.addEdge(MV-2, i, 1);
    FR(i, n) dinic.addEdge(n+n+i, MV-1, 1);

    FR(i, n) dinic.addEdge(n+i, n+n+i, 1);
    int res = dinic.maxFlow(MV-2, MV-1);
    assert(res <= g);
    if(res != g) return !printf("-1\n");
    dinic.reset();
    FR(i, n) dinic.rmEdge(n+i, n+n+i);

    //dbgArr(edges, SZ(edges));

    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;
    }
    //dbgArr(inAns, SZ(edges));
    cout << ans << '\n';
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3484kb

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: 0
Accepted
time: 2ms
memory: 3408kb

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:

429

result:

ok answer is '429'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

10 43 3
1 3 656
2 6 856
4 10 99
5 6 900
2 7 766
4 7 582
2 8 135
5 7 831
3 5 12
3 10 789
1 8 66
4 9 390
1 7 238
6 7 960
1 4 624
3 9 602
7 10 366
5 8 526
2 9 561
6 10 722
2 5 904
3 4 35
1 9 768
5 9 457
6 8 61
4 6 192
4 5 96
5 10 747
8 9 611
7 8 953
3 8 449
2 4 228
1 6 197
9 10 160
3 6 869
1 2 785
4 8 ...

output:

526

result:

ok answer is '526'

Test #4:

score: -100
Runtime Error

input:

277 9038 1
226 260 740
44 226 376
151 263 611
67 269 241
120 181 677
259 271 782
37 52 310
48 152 452
168 266 823
85 234 100
46 201 738
129 153 301
69 147 434
13 72 764
13 234 316
171 222 398
214 255 21
112 158 430
20 118 407
45 152 971
205 214 272
221 275 362
198 268 472
117 176 207
31 75 652
139 1...

output:


result: