QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107892 | #1825. The King's Guards | BalintR | RE | 2ms | 3484kb | C++20 | 5.2kb | 2023-05-23 05:32:48 | 2023-05-23 05:32:53 |
Judging History
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...