Submission #84494

#	Time	Username	Problem	Language	Result	Execution time	Memory
84494		Flying_dragon_02	Pipes (BOI13_pipes)	C++14	100 / 100	315 ms	30136 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 1e5 + 5;

int n, m, c[N], deg[N], a[N], b[N];
long long x[N];

ii par[N];

vector<ii> graph[N];

bool vis[N], in[N];

vector<int> cycle;

void dfs(int u, int p, int type) {
    vis[u] = 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i].fi;
        if(v == p) continue;
        if(vis[v] && type == 0 && in[v] == 0) {
            int z = u;
            while(z != v) {
                if(z == 0) break;
                cycle.pb(z);
                in[z] = 1;
                z = par[z].fi;
            }
            in[v] = 1;
            cycle.pb(v);
            continue;
        }
        if(vis[v]) continue;
        par[v] = {u, graph[u][i].se};
        dfs(v, u, type);
    }
    if(type == 1) {
        if(in[u] == 0) {
            ii lmao = par[u];
            x[lmao.se] = 2 * c[u];
            c[lmao.fi] = c[lmao.fi] - c[u];
            c[u] = 0;
        }
    }
}

void bfs(int u, int p) {
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i].fi;
        if(v == p) continue;
        bfs(v, u);
    }
    if(u != 1) {
        ii lmao = par[u];
        x[lmao.se] = 2 * c[u];
        c[lmao.fi] = c[lmao.fi] - c[u];
        c[u] = 0;
    }
}

void bye() {
    cout << "0\n";
    exit(0);
}

map<ii, int> edge;

queue<int> q;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    if(n < m)
        bye();
    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        edge[{a[i], b[i]}] = i;
        edge[{b[i], a[i]}] = i;
        ++deg[a[i]]; ++deg[b[i]];
        graph[a[i]].pb({b[i], i});
        graph[b[i]].pb({a[i], i});
    }
    dfs(1, 1, 0);
    memset(vis, 0, sizeof(vis));
    if(n == m + 1) {
        bfs(1, 1);
        if(c[1] != 0)
            bye();
        for(int i = 1; i <= m; i++)
            cout << x[i] << "\n";
        exit(0);
    }
    if(cycle.size() % 2 == 0)
        bye();
    dfs(cycle[0], cycle[0], 1);
    long long total = 0, s = cycle.size() - 1;
    for(int i = 0; i < cycle.size(); i++) {
        if(i % 2 == 0)
            total += c[cycle[i]];
        else
            total -= c[cycle[i]];
    }
    x[edge[{cycle[0], cycle[s]}]] = total;
    if(total % 2 != 0)
        bye();
    c[cycle[0]] -= total / 2;
    c[cycle[s]] -= total / 2;
    for(int i = 0; i < cycle.size() - 1; i++) {
        x[edge[{cycle[i], cycle[i + 1]}]] = 2 * c[cycle[i]];
        c[cycle[i + 1]] = c[cycle[i + 1]] - c[cycle[i]];
        c[cycle[i]] = 0;
    }
    if(c[cycle[s]] != 0)
        bye();
    for(int i = 1; i <= m; i++) {
        if(x[i] > 1000000000 || x[i] < -1000000000)
            bye();
    }
    for(int i = 1; i <= n; i++) {
        if(c[i])
            bye();
    }
    for(int i = 1; i <= m; i++)
       cout << x[i] << "\n";
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int, int)':
pipes.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void bfs(int, int)':
pipes.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size(); i++) {
                    ~~^~~~~~~~~~~~~~
pipes.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size() - 1; i++) {
                    ~~^~~~~~~~~~~~~~~~~~

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