QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225582#3855. Regional developmentEnergy_is_not_over#RE 0ms0kbC++173.0kb2023-10-24 20:14:482023-10-24 20:14:49

Judging History

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

  • [2023-10-24 20:14:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-24 20:14:48]
  • 提交

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) {
        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();
        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(To[i]);
        g[To[i]].push_back(From[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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

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:


result: