Submission #698544

#	Time	Username	Problem	Language	Result	Execution time	Memory
698544		_martynas	Pipes (BOI13_pipes)	C++11	100 / 100	185 ms	18760 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int MXN = 1e5+5;

int n, m;
ll C[MXN];
vector<pii> adj[MXN];
int degree[MXN];
ll E[5*MXN];
bool visited[MXN];

void dfs(int u, vi &comp) {
    visited[u] = true;
    comp.PB(u);
    for(auto p : adj[u]) {
        int v = p.F;
        if(visited[v] || !degree[v]) continue;
        dfs(v, comp);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> C[i];
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[a].PB({b, i});
        adj[b].PB({a, i});
    }
    queue<int> Q;
    for(int i = 1; i <= n; i++) {
        degree[i] = adj[i].size();
        if(degree[i] == 1) Q.push(i);
    }
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        degree[u] = 0;
        for(auto p : adj[u]) {
            if(degree[p.F]) {
                // there should only be one v that satisfies this condition
                E[p.S] = C[u];
                degree[p.F]--;
                C[p.F] -= C[u];
                if(degree[p.F] == 1) Q.push(p.F);
            }
        }
    }
    // all remaining vertices should be disjoint cycles of odd length
    for(int i = 1; i <= n; i++) {
        if(degree[i] != 0 && degree[i] != 2) {
            cout << "0\n";
            return 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(degree[i] && !visited[i]) {
            vi comp;
            dfs(i, comp);
            cerr << comp.size() << "\n";
            if(comp.size() % 2 == 0) {
                cout << "0\n";
                return 0;
            }
            ll sum = 0;
            for(int u : comp) sum += C[u];
            sum /= 2;
            // keep edge cost between 0 and 1
            for(int u = 2; u < comp.size(); u += 2) {
                sum -= C[comp[u]];
            }
            ll last = 0;
            for(auto p : adj[comp[0]]) {
                if(p.F == comp[1]) {
                    E[p.S] = sum;
                    last = E[p.S];
                }
            }
            for(int u = 1; u < comp.size(); u++) {
                for(auto p : adj[comp[u]]) {
                    if(p.F == comp[(u+1)%comp.size()]) {
                        E[p.S] = C[comp[u]]-last;
                        last = E[p.S];
                    }
                }
            }
        }
    }
    for(int i = 0; i < m; i++) {
        cout << 2*E[i] << "\n";
    }
    return 0;
}
/*
3 2
1 2 1
1 2
2 3

3 3
8 10 12
1 2
2 3
1 3

3 7 5
*/

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int u = 2; u < comp.size(); u += 2) {
      |                            ~~^~~~~~~~~~~~~
pipes.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int u = 1; u < comp.size(); u++) {
      |                            ~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70