oj.uz

Submission #1077680

# Submission time Handle Problem Language Result Execution time Memory
1077680 2024-08-27T08:34:32 Z TVSown Pipes (BOI13_pipes) C++17
74.0741 / 100
 138 ms 70868 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);
        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){
//            cout << u << " " << deg[u] << "\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[v] -= c[u];
                --deg[v];
                if(deg[v] == 1){
//                    cout << u << " " << v << "\n";
                    q.push(v);
                }
            }
        }
        int cnt = 0;
        FOR(u, 1, 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:119:5: note: in expansion of macro 'inp'
  119 |     inp("in.txt");
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25436 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 40 ms 32512 KB Output is correct
5 Correct 5 ms 25432 KB Output is correct
6 Correct 7 ms 25436 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 5 ms 25436 KB Output is correct
9 Correct 5 ms 25600 KB Output is correct
10 Correct 6 ms 25692 KB Output is correct
11 Correct 6 ms 25692 KB Output is correct
12 Correct 6 ms 25692 KB Output is correct
13 Correct 33 ms 31068 KB Output is correct
14 Correct 39 ms 32084 KB Output is correct
15 Correct 45 ms 32348 KB Output is correct
16 Correct 34 ms 31308 KB Output is correct
17 Correct 49 ms 32472 KB Output is correct
18 Correct 46 ms 32476 KB Output is correct
19 Correct 42 ms 35664 KB Output is correct
20 Correct 5 ms 25436 KB Output is correct
21 Correct 5 ms 25692 KB Output is correct
22 Correct 38 ms 32508 KB Output is correct
23 Correct 32 ms 31060 KB Output is correct
24 Correct 41 ms 32340 KB Output is correct
25 Correct 33 ms 31164 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 6 ms 25692 KB Output isn't correct
3 Correct 30 ms 31880 KB Output is correct
4 Correct 31 ms 31068 KB Output is correct
5 Correct 30 ms 31428 KB Output is correct
6 Correct 138 ms 46360 KB Output is correct
7 Incorrect 6 ms 25436 KB Output isn't correct
8 Incorrect 5 ms 25436 KB Output isn't correct
9 Correct 4 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 5 ms 25436 KB Output is correct
12 Correct 5 ms 25436 KB Output is correct
13 Correct 5 ms 25664 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 25692 KB Output isn't correct
17 Correct 5 ms 25688 KB Output is correct
18 Correct 6 ms 25688 KB Output is correct
19 Correct 5 ms 25692 KB Output is correct
20 Correct 5 ms 25500 KB Output is correct
21 Correct 5 ms 25784 KB Output is correct
22 Incorrect 6 ms 25688 KB Output isn't correct
23 Runtime error 63 ms 68268 KB Execution killed with signal 11
24 Runtime error 62 ms 70868 KB Execution killed with signal 11
25 Correct 34 ms 31828 KB Output is correct
26 Correct 34 ms 31060 KB Output is correct
27 Correct 30 ms 31068 KB Output is correct
28 Correct 34 ms 31496 KB Output is correct
29 Correct 95 ms 42448 KB Output is correct
30 Runtime error 63 ms 68812 KB Execution killed with signal 11
31 Incorrect 43 ms 38088 KB Output isn't correct
32 Runtime error 64 ms 66384 KB Execution killed with signal 11
33 Correct 37 ms 32080 KB Output is correct
34 Correct 30 ms 31056 KB Output is correct
35 Correct 43 ms 31316 KB Output is correct
36 Correct 32 ms 31320 KB Output is correct
37 Correct 110 ms 46424 KB Output is correct
38 Runtime error 64 ms 69600 KB Execution killed with signal 11
39 Runtime error 80 ms 65476 KB Execution killed with signal 11
40 Runtime error 63 ms 70092 KB Execution killed with signal 11
41 Correct 32 ms 31824 KB Output is correct
42 Correct 28 ms 31060 KB Output is correct
43 Correct 30 ms 31068 KB Output is correct
44 Correct 39 ms 31304 KB Output is correct
45 Correct 88 ms 43600 KB Output is correct
46 Runtime error 64 ms 68308 KB Execution killed with signal 11
47 Runtime error 64 ms 70428 KB Execution killed with signal 11
48 Incorrect 49 ms 37840 KB Output isn't correct
49 Correct 35 ms 32084 KB Output is correct
50 Correct 30 ms 31316 KB Output is correct
51 Correct 33 ms 31424 KB Output is correct
52 Correct 29 ms 31056 KB Output is correct
53 Correct 91 ms 43552 KB Output is correct
54 Runtime error 64 ms 68084 KB Execution killed with signal 11