QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#346799	#3855. Regional development	Kirill22^#	TL	2012ms	5888kb	C++23	2.3kb	2024-03-08 23:52:32	2024-03-08 23:52:32

Judging History

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

[2024-03-08 23:52:32]
评测

测评结果：TL
用时：2012ms
内存：5888kb

查看

[2024-03-08 23:52:32]
提交

answer

#include "bits/stdc++.h"

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, mod;
    cin >> n >> m >> mod;
    vector<int> a(m), b(m), c(m), tmp(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
        tmp[a[i]] += c[i];
        tmp[b[i]] -= c[i];
        g[a[i]].push_back(i);
        g[b[i]].push_back(i);
    }
    for (int v = 0; v < n; v++) {
        while (tmp[v] > 0) {
            bool find = false;
            vector<int> stk, res;
            set<pair<int, int>> usd;
            function<void(int, int)> dfs = [&] (int v, int pr) {
                if (!usd.insert({v, pr}).second) {
                    return;
                }
                if (find) {
                    return;
                }
                if (tmp[v] < 0) {
                    find = true;
                    res = stk;
                    return;
                }
                for (auto i : g[v]) {
                    if (i == pr) {
                        continue;
                    }
                    int u = a[i] ^ b[i] ^ v;
                    if (v == a[i]) {
                        if (c[i] > 0) {
                            stk.push_back(i);
                            dfs(u, i);
                            stk.pop_back();
                        }
                    } else {
                        if (c[i] < 0) {
                            stk.push_back(i);
                            dfs(u, i);
                            stk.pop_back();
                        }
                    }
                }
            };
            dfs(v, -1);
            for (auto i : res) {
                tmp[a[i]] -= c[i];
                tmp[b[i]] += c[i];
                if (c[i] > 0) {
                    c[i] = c[i] - mod;
                } else {
                    c[i] = c[i] + mod;
                }
                tmp[a[i]] += c[i];
                tmp[b[i]] -= c[i];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        assert(tmp[i] == 0);
    }
    for (int i = 0; i < m; i++) {
        assert(c[i] != 0 && -mod < c[i] && c[i] < mod);
        cout << c[i] << '\n';
    }
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3540kb

input:

output:

result:

ok correct plan

Test #2:

score: 0

Accepted

time: 30ms

memory: 4028kb

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:

result:

ok correct plan

Test #3:

score: 0

Accepted

time: 39ms

memory: 4072kb

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:

result:

ok correct plan

Test #4:

score: 0

Accepted

time: 59ms

memory: 4096kb

input:

output:

-1
-1
1
-1
-1
-1
-1
2
1
1
-1
-2
2
2
-1
2
-2
1
1
-1
2
-1
-1
1
-1
-2
2
1
-1
1
-1
-2
1
2
1
-1
-2
-2
-1
-1
1
-2
2
1
1
-2
-1
-2
-1
-1
1
-1
2
-2
-1
-2
1
-2
2
2
1
-2
2
1
-1
1
-1
-1
1
1
-1
-1
-2
2
1
2
1
2
2
-1
2
-2
2
-1
1
1
2
-2
-2
2
-2
-2
2
-2
2
1
-2
-2
1
-1
1
2
1
-2
2
-2
-2
1
1
2
-1
1
1
-2
-1
1
-1
-1
1
-1...

result:

ok correct plan

Test #5:

score: 0

Accepted

time: 2012ms

memory: 5888kb

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:

result:

ok correct plan

Test #6:

score: 0

Accepted

time: 1ms

memory: 3560kb

input:

output:

result:

ok correct plan

Test #7:

score: -100

Time Limit Exceeded

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...