oj.uz

Submission #1077709

# Submission time Handle Problem Language Result Execution time Memory
1077709 2024-08-27T08:40:34 Z TVSown Pipes (BOI13_pipes) C++17
74.0741 / 100
 119 ms 69100 KB 
///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, m;
int ans[N], c[N], deg[N];
vector<pi> e[N];

namespace sub1{
    void dfs(int u, int p){
        for(auto [v, i] : e[u]){
            if(v == p) continue;
            dfs(v, u);
            ans[i] = 2 * c[v];
            c[u] -= c[v];
        }
    }

    void solve(){
        dfs(1, 0);
        FOR(i, 1, m) cout << ans[i] << "\n";
    }
}

namespace sub2{
    int vst[N], root, A, B;
    vector<int> st;
    queue<int> q;
    void dfs(int u, int p, int type){
        st.pb(u);
//        cout << u << "\n";
        vst[u] = 1;
        if(type) A += c[u];
        else B += c[u];
        for(auto [v, i] : e[u]){
            if(vst[v]) continue;
            dfs(v, u, type ^ 1);
        }
    }

    void solve(){
        FOR(u, 1, n){
            if(deg[u] == 1) q.push(u);
        }
        while(szz(q)){
            int u = q.front(); q.pop();
            vst[u] = 1;
            for(auto [v, i] : e[u]){
                if(vst[v]) continue;
                ans[i] += 2 * c[u];
                c[u] -= c[u];
                c[v] -= c[u];
                --deg[v];
                if(deg[v] == 1){
                    q.push(v);
                }
            }
        }
        int cnt = 0;
        FOR(u, 1, n){
//            cout << c[u] << "\n";
            if(!vst[u]){
//                cout << u << "\n";
                ++cnt; root = u;
            }
        }
        if(cnt % 2 == 0){
            cout << 0; return;
        }
        dfs(root, 0, 1);
        st.pb(root);
        FOR(i, 0, szz(st) - 2){
            int u = st[i];
            for(auto [v, i] : e[u]){
                if(v == st[i + 1]){
                    if(i % 2) ans[i] = B - A;
                    else ans[i] = A - B;
                }
            }
        }

        FOR(i, 1, n) cout << ans[i] << "\n";
    }
}

void solve(){
    cin >> n >> m;
    FOR(u, 1, n) cin >> c[u];
    FOR(i, 1, m){
        int u, v; cin >> u >> v;
        e[u].pb({v, i});
        e[v].pb({u, i});
        ++deg[u];
        ++deg[v];
    }
    if(m == n - 1) sub1::solve();
    else if(m > n) cout << 0;
    else sub2::solve();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("in.txt");
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:17:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
pipes.cpp:120:5: note: in expansion of macro 'inp'
  120 |     inp("in.txt");
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25692 KB Output is correct
4 Correct 37 ms 30756 KB Output is correct
5 Correct 5 ms 25616 KB Output is correct
6 Correct 5 ms 25436 KB Output is correct
7 Correct 5 ms 25548 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 6 ms 25692 KB Output is correct
10 Correct 6 ms 25692 KB Output is correct
11 Correct 5 ms 25692 KB Output is correct
12 Correct 7 ms 25692 KB Output is correct
13 Correct 32 ms 29768 KB Output is correct
14 Correct 38 ms 30556 KB Output is correct
15 Correct 41 ms 30812 KB Output is correct
16 Correct 42 ms 29956 KB Output is correct
17 Correct 40 ms 30892 KB Output is correct
18 Correct 38 ms 30744 KB Output is correct
19 Correct 52 ms 34164 KB Output is correct
20 Correct 6 ms 25432 KB Output is correct
21 Correct 5 ms 25692 KB Output is correct
22 Correct 38 ms 30804 KB Output is correct
23 Correct 30 ms 29784 KB Output is correct
24 Correct 45 ms 30780 KB Output is correct
25 Correct 31 ms 30036 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 25436 KB Output isn't correct
2 Incorrect 5 ms 25692 KB Output isn't correct
3 Correct 32 ms 30300 KB Output is correct
4 Correct 32 ms 29532 KB Output is correct
5 Correct 39 ms 29680 KB Output is correct
6 Correct 109 ms 40104 KB Output is correct
7 Incorrect 5 ms 25436 KB Output isn't correct
8 Incorrect 5 ms 25432 KB Output isn't correct
9 Correct 5 ms 25436 KB Output is correct
10 Correct 9 ms 25436 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct
13 Correct 8 ms 25412 KB Output is correct
14 Incorrect 5 ms 25436 KB Output isn't correct
15 Incorrect 5 ms 25692 KB Output isn't correct
16 Incorrect 5 ms 25688 KB Output isn't correct
17 Correct 8 ms 25524 KB Output is correct
18 Correct 6 ms 25692 KB Output is correct
19 Correct 7 ms 25436 KB Output is correct
20 Correct 5 ms 25688 KB Output is correct
21 Correct 9 ms 25748 KB Output is correct
22 Incorrect 6 ms 25552 KB Output isn't correct
23 Runtime error 54 ms 66988 KB Execution killed with signal 11
24 Runtime error 75 ms 69100 KB Execution killed with signal 11
25 Correct 42 ms 30388 KB Output is correct
26 Correct 38 ms 29636 KB Output is correct
27 Correct 40 ms 29548 KB Output is correct
28 Correct 37 ms 29920 KB Output is correct
29 Correct 88 ms 37512 KB Output is correct
30 Runtime error 63 ms 67296 KB Execution killed with signal 11
31 Incorrect 47 ms 36556 KB Output isn't correct
32 Runtime error 62 ms 64848 KB Execution killed with signal 11
33 Correct 47 ms 30548 KB Output is correct
34 Correct 34 ms 29532 KB Output is correct
35 Correct 35 ms 29680 KB Output is correct
36 Correct 34 ms 29808 KB Output is correct
37 Correct 119 ms 40268 KB Output is correct
38 Runtime error 63 ms 68076 KB Execution killed with signal 11
39 Runtime error 81 ms 63824 KB Execution killed with signal 11
40 Runtime error 75 ms 68620 KB Execution killed with signal 11
41 Correct 46 ms 30268 KB Output is correct
42 Correct 31 ms 29564 KB Output is correct
43 Correct 39 ms 29520 KB Output is correct
44 Correct 37 ms 29780 KB Output is correct
45 Correct 108 ms 38200 KB Output is correct
46 Runtime error 65 ms 66772 KB Execution killed with signal 11
47 Runtime error 65 ms 68812 KB Execution killed with signal 11
48 Incorrect 43 ms 36304 KB Output isn't correct
49 Correct 32 ms 30548 KB Output is correct
50 Correct 34 ms 29524 KB Output is correct
51 Correct 31 ms 29788 KB Output is correct
52 Correct 33 ms 29524 KB Output is correct
53 Correct 95 ms 38228 KB Output is correct
54 Runtime error 62 ms 66672 KB Execution killed with signal 11