QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225584 | #3855. Regional development | Energy_is_not_over# | AC ✓ | 225ms | 3984kb | C++17 | 3.1kb | 2023-10-24 20:21:13 | 2023-10-24 20:21:14 |
Judging History
answer
//
// Stvoreno Energom o 24.10.23. 13:48:00
//
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
#ifdef Energy_is_not_over
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)
#define LOG(...) print(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (0)
#define LOG(...)
#endif
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int max_n = 1011, inf = 1000111222;
const int max_m = 10011;
int n, m, mod, bal[max_n];
int From[max_m], To[max_m], val[max_m];
vector<int> g[max_n];
int parent[max_n];
queue<int> q;
bool augment() {
bool has_start = false;
for (int i = 0; i < n; ++i) {
// LOG(i, bal[i]);
parent[i] = -1;
if (bal[i] > 0) {
// assert(bal[i] % mod == 0);
parent[i] = -2;
q.push(i);
has_start = true;
}
}
if (!has_start) {
return false;
}
while (!q.empty()) {
int v = q.front();
q.pop();
// LOG(v, bal[v]);
for (int id : g[v]) {
const int to = v ^ From[id] ^ To[id];
if ((val[id] > 0) == (From[id] == v)) {
if (parent[to] == -1) {
parent[to] = id;
q.push(to);
}
}
}
}
int finish = -1;
for (int i = 0; i < n; ++i) {
if (bal[i] < 0 && parent[i] >= 0) {
finish = i;
break;
}
}
assert(finish != -1);
// cout << finish << " " << parent[finish] << " ";
bal[finish] += mod;
while (parent[finish] != -2) {
const int id = parent[finish];
// cout << "$" << id << "%" << endl;
if (val[id] > 0) {
val[id] -= mod;
} else {
val[id] += mod;
}
finish ^= From[id] ^ To[id];
}
// cout << finish << endl;
bal[finish] -= mod;
return true;
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> mod;
for (int i = 0; i < m; ++i) {
cin >> From[i] >> To[i] >> val[i];
--From[i];
--To[i];
g[From[i]].push_back(i);
g[To[i]].push_back(i);
bal[From[i]] += val[i];
bal[To[i]] -= val[i];
}
while (augment()) {
// DEBUG {
// for (int i = 0; i < m; ++i) {
// cout << val[i] << " ";
// }
// cout << " ";
// for (int i = 0; i < n; ++i) {
// cout << bal[i] << " ";
// }
// cout << endl;
// }
}
for (int i = 0; i < m; ++i) {
cout << val[i] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
10 23 3 2 10 1 2 6 1 6 9 1 7 9 1 6 7 1 3 6 1 1 3 1 1 6 2 6 10 1 2 9 1 4 9 2 4 7 2 3 10 2 3 9 1 6 8 1 7 8 2 3 5 1 5 9 1 8 9 2 3 8 2 1 5 2 1 4 1 5 10 2
output:
1 1 1 1 1 1 -2 -1 -2 -2 -1 2 -1 -2 1 2 1 1 2 -1 2 1 2
result:
ok correct plan
Test #2:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
100 1297 11 27 34 5 7 34 6 7 90 3 80 90 6 37 80 6 37 48 5 47 48 6 47 86 5 56 86 6 56 84 5 63 84 6 38 63 6 66 91 8 12 91 6 12 15 5 15 22 1 22 87 5 46 87 6 46 63 10 63 87 8 71 87 6 65 71 6 38 65 1 38 67 4 29 67 6 9 29 6 9 21 5 16 21 6 16 89 2 89 98 5 4 98 6 4 13 4 13 33 5 14 33 6 14 66 10 66 86 10 57 ...
output:
5 6 -8 6 6 5 6 -6 6 5 -5 6 8 -5 -6 1 -6 -5 10 8 6 6 1 4 6 6 -6 6 -9 5 6 4 5 6 -1 10 6 6 5 7 -5 -5 8 5 6 5 5 6 6 5 6 5 6 1 6 3 5 -5 5 -6 6 8 9 6 8 5 -5 -6 -6 -5 6 -6 6 6 5 -5 5 6 -5 5 -5 -6 10 6 7 -6 5 -5 7 5 -6 6 6 -6 -6 6 -5 6 -6 5 -1 -6 5 -5 6 5 5 -4 -5 6 -6 5 8 5 -5 -6 5 5 5 6 -6 -5 -9 -5 5 6 1 -...
result:
ok correct plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
100 1272 18 39 40 14 39 95 4 21 95 14 12 21 14 12 82 16 28 82 14 17 28 14 17 67 5 35 67 14 11 35 1 11 67 15 17 58 4 58 80 4 28 80 14 28 77 3 25 77 10 22 25 14 22 54 4 13 54 14 13 99 4 86 99 14 86 89 16 21 89 14 21 62 4 16 62 14 16 81 4 76 81 14 56 76 1 28 56 14 28 47 4 19 47 14 19 91 4 22 91 14 13 2...
output:
14 -14 -4 14 -2 14 14 -13 14 1 -3 4 4 -4 3 -8 14 4 14 4 14 16 -4 4 14 -14 14 1 -4 4 14 -14 -4 14 -14 4 14 14 4 -14 13 4 2 -4 4 -14 14 4 17 14 4 4 -4 -9 -4 4 14 14 -1 4 4 14 -14 4 4 14 14 4 4 14 -4 4 -16 -14 9 -14 4 -4 10 -14 4 -4 -17 14 11 14 4 -4 10 4 8 4 14 -8 14 -4 4 -4 4 14 4 4 14 4 17 -17 17 11...
result:
ok correct plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3976kb
input:
100 1350 3 22 75 2 22 50 2 22 35 1 25 35 2 42 76 2 39 42 2 36 39 2 14 36 2 14 33 1 33 72 1 54 72 2 54 73 1 5 73 2 45 92 2 23 92 2 23 26 2 26 62 1 6 62 1 22 86 1 24 86 2 7 24 2 7 55 2 20 39 2 20 73 1 27 73 2 27 68 1 24 68 2 24 98 1 8 98 2 8 33 1 3 33 2 1 3 1 3 97 1 83 97 2 83 90 1 38 90 2 38 86 1 21 ...
output:
-1 2 1 2 2 2 2 2 1 -2 2 1 -1 -1 -1 2 1 -2 -2 2 2 2 2 -2 -1 1 2 -2 2 1 2 1 1 2 1 -1 1 1 2 2 -2 -2 2 1 -2 1 2 -2 2 -1 1 2 2 1 2 1 1 -2 2 2 -2 1 -1 1 2 -2 2 -1 1 -2 -1 2 -2 2 1 2 -2 2 2 -1 2 1 -1 2 -2 1 2 1 -2 -1 1 1 -1 -2 -1 1 1 1 -2 2 1 -1 1 1 -1 -2 1 -2 1 -1 2 1 1 1 2 1 2 -1 1 -1 -2 2 1 2 1 1 2 2 -2...
result:
ok correct plan
Test #5:
score: 0
Accepted
time: 225ms
memory: 3896kb
input:
1000 9780 26 39 260 1 215 260 25 215 483 1 483 801 1 801 977 1 379 977 25 316 379 25 316 732 1 474 732 25 183 474 25 177 183 25 177 788 1 525 788 25 525 909 1 51 909 25 51 565 1 203 565 25 203 353 1 353 655 8 655 814 1 814 999 1 305 999 25 52 305 25 52 978 20 839 978 25 646 839 25 536 646 25 536 571...
output:
1 25 1 1 -25 -1 -1 -25 25 25 25 -25 25 -25 -1 -25 25 -25 -18 1 1 25 25 20 25 25 25 1 25 -25 -1 1 25 1 25 25 -25 13 25 1 1 25 25 25 1 1 -25 -1 1 -1 1 1 25 -25 -1 -25 25 25 -25 25 1 25 25 1 -25 -1 -25 -1 1 -1 -25 25 25 25 -25 1 25 1 25 1 -1 1 25 1 25 1 25 15 25 25 -1 1 1 25 25 1 25 1 25 1 1 1 1 25 1 1...
result:
ok correct plan
Test #6:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
20 190 20 2 7 10 4 7 18 4 19 15 1 19 14 1 2 13 1 13 10 3 13 10 1 3 12 8 10 19 10 12 13 12 16 12 8 16 9 3 19 18 2 19 5 2 17 15 4 17 2 4 5 3 1 5 8 14 19 16 4 14 15 19 20 7 13 20 11 3 20 8 7 9 14 9 13 16 13 16 14 1 16 19 1 14 14 8 14 1 3 8 3 3 9 8 9 17 1 17 19 10 1 20 1 10 20 17 4 10 5 4 6 14 6 19 16 1...
output:
10 18 -5 -6 13 -10 -10 12 19 13 12 -11 -2 -15 -5 -18 3 8 16 -5 7 11 8 14 16 14 -1 -6 1 3 8 1 10 -19 -3 5 14 -4 -7 17 4 9 7 13 10 2 8 7 -12 1 -15 17 -4 2 16 13 17 15 11 -4 17 -11 17 14 -5 1 3 3 -6 6 -8 2 -2 -13 -1 1 -8 -5 10 10 -1 9 12 12 10 13 13 11 -8 16 17 9 6 2 18 -18 -3 14 18 10 -9 3 -5 2 16 8 5...
result:
ok correct plan
Test #7:
score: 0
Accepted
time: 170ms
memory: 3952kb
input:
300 9997 94 3 81 59 80 81 43 40 80 43 40 121 51 121 151 51 95 151 47 95 158 59 149 158 43 149 258 51 99 258 43 99 150 51 150 299 51 29 299 43 29 151 5 151 289 51 13 289 43 13 226 51 182 226 30 182 248 51 6 248 17 6 243 51 91 243 43 91 193 51 169 193 43 169 287 51 237 287 43 153 237 31 153 289 51 155...
output:
59 43 43 51 51 -47 59 43 51 -51 51 -43 43 5 51 -51 -43 30 51 -77 -43 -51 51 43 51 43 31 51 -51 51 43 -51 -43 43 86 51 43 51 43 43 -71 51 43 51 51 43 -51 -43 -65 -43 -51 -43 43 51 51 43 51 -51 -43 43 -43 43 51 51 51 -51 51 43 43 51 51 -51 43 51 51 43 -51 43 51 51 51 43 51 43 -43 43 43 32 43 43 43 -43...
result:
ok correct plan
Test #8:
score: 0
Accepted
time: 20ms
memory: 3764kb
input:
100 4950 497 11 84 473 37 84 457 37 44 399 7 44 434 7 97 276 11 97 299 42 75 227 75 96 345 10 96 6 10 64 345 64 91 15 16 91 390 3 16 431 3 8 449 2 8 129 2 83 360 83 86 430 22 86 377 22 26 354 8 26 30 8 60 386 60 69 473 35 69 181 18 35 161 18 40 246 12 40 100 12 18 224 18 57 312 55 57 253 55 97 417 6...
output:
-24 -40 -98 -63 -221 -198 227 345 -491 -152 15 -107 431 449 -368 -137 430 -120 354 30 -111 473 -316 161 -251 100 224 -185 253 417 473 418 51 18 -180 -255 456 214 -9 15 -65 413 300 318 -233 169 -286 99 440 477 170 220 90 -30 375 126 74 -183 63 -49 157 201 -109 -254 479 -281 -44 35 -105 53 -130 -69 27...
result:
ok correct plan
Test #9:
score: 0
Accepted
time: 58ms
memory: 3984kb
input:
1000 10000 2 403 261 1 423 168 1 977 444 1 298 748 1 77 687 1 229 276 1 791 650 1 39 507 1 747 612 1 882 369 1 376 1000 1 812 953 1 713 123 1 403 749 1 215 394 1 342 218 1 691 673 1 33 289 1 437 652 1 217 223 1 247 665 1 701 192 1 229 726 1 18 850 1 585 343 1 407 925 1 940 382 1 920 851 1 901 740 1 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok correct plan
Test #10:
score: 0
Accepted
time: 6ms
memory: 3688kb
input:
1000 1935 4 860 820 1 102 103 1 910 911 1 230 190 1 234 235 3 151 150 1 506 507 1 528 568 1 273 313 1 149 150 1 798 758 1 597 557 1 610 650 1 746 747 1 63 23 3 102 142 3 619 620 1 81 41 3 238 278 1 760 759 1 799 798 1 853 852 1 193 194 3 199 239 1 150 190 1 876 916 1 996 997 2 244 243 1 282 242 1 27...
output:
-3 1 1 -3 3 1 1 1 1 1 -3 1 1 -3 -1 -1 -3 -1 1 1 1 1 3 1 1 1 -2 1 -3 -3 -3 -3 1 1 -3 1 1 -3 1 1 1 1 1 1 1 -3 1 3 1 3 -3 1 3 -3 1 1 1 -1 3 1 -1 1 -1 1 1 1 -3 1 1 -1 1 1 1 3 1 3 -1 3 -3 1 1 1 3 1 1 -1 3 1 -3 -1 -3 -1 1 -1 3 1 1 1 1 -3 -3 3 1 3 3 1 -3 -1 3 1 3 1 3 1 1 3 2 -3 1 3 1 1 3 -1 -3 3 3 1 1 1 -3...
result:
ok correct plan