Submission #79873

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
79873	2018-10-17T03:05:04 Z	win11905	Pipes (BOI13_pipes)	C++11	Compilation error	0 ms	0 KB

pipes

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;

int n, m, s[N], t[N];
int A[N], deg[N];
int ans[N];

set<int> g[N];

void answer() {
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    exit(0);
}

void solve() {
    queue<int> Q;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) Q.emplace(i);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int x : g[u]) {
            int v = u ^ s[x] ^ t[x]; 
            g[v].erase(x);
            A[v] -= A[u];
            ans[x] = A[u] << 1;
            if(g[v].size() == 1) Q.emplace(v);
        }
        g[u].clear();
    }
}

int cnt = 0;

void dfs(int u, int p) {
    static int idx = 0;
    static int sum = 0;
    idx++;
    if(idx & 1) sum += A[u];
    else sum -= A[u];
    for(auto i : g[u]) {
        int v = u ^ s[i] ^ t[i];
        if(v != p) {
            if(cnt == sum) {
                ans[i] = sum;
                A[u] -= sum / 2, A[v] -= sum / 2;
                return;
            }
            dfs(v, u);
        }
    }
    if(cnt == sum) {
        if(g[u][0] == p) swap(g[u][0], g[u][1]);
        int v = u ^ s[g[u][0]] ^ t[g[u][0]];
        g[v].erase(g[u][0]);
        g[u].erase(g[u][0]);
    } 
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d", s+i, t+i);
        g[s[i]].emplace(i), g[t[i]].emplace(i);
        deg[s[i]]++, deg[t[i]]++;
    }
    if(n < m) return puts("0"), 0;
    solve(); 
    if(n == m+1) answer();
    for(int i = 1; i <= n; ++i) if(g[i].size()) cnt++;
    if(cnt % 2 == 0) return puts("0"), 0;
    for(int i = 1; i <= n; ++i) {
        if(g[i].size()) dfs(i, i);
        break;
    }
    solve();
    answer();
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:53:16: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         if(g[u][0] == p) swap(g[u][0], g[u][1]);
                ^
pipes.cpp:53:35: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         if(g[u][0] == p) swap(g[u][0], g[u][1]);
                                   ^
pipes.cpp:53:44: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         if(g[u][0] == p) swap(g[u][0], g[u][1]);
                                            ^
pipes.cpp:54:27: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         int v = u ^ s[g[u][0]] ^ t[g[u][0]];
                           ^
pipes.cpp:54:40: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         int v = u ^ s[g[u][0]] ^ t[g[u][0]];
                                        ^
pipes.cpp:55:24: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         g[v].erase(g[u][0]);
                        ^
pipes.cpp:56:24: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
         g[u].erase(g[u][0]);
                        ^
pipes.cpp: In function 'int main()':
pipes.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:62:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
pipes.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", s+i, t+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~