oj.uz

Submission #1077721

# Submission time Handle Problem Language Result Execution time Memory
1077721 2024-08-27T08:42:30 Z TVSown Pipes (BOI13_pipes) C++17
74.0741 / 100
 113 ms 76108 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) (s.size())
#define int long long
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 'void sub2::solve()':
pipes.cpp:15:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define FOR(i, a, b) for(int i = a; i <= b; ++i)
......
   89 |         FOR(i, 0, szz(st) - 2){
      |             ~~~~~~~~~~~~~~~~~          
pipes.cpp:89:9: note: in expansion of macro 'FOR'
   89 |         FOR(i, 0, szz(st) - 2){
      |         ^~~
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:121:5: note: in expansion of macro 'inp'
  121 |     inp("in.txt");
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25432 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 8 ms 25432 KB Output is correct
4 Correct 47 ms 33152 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 8 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 9 ms 25228 KB Output is correct
9 Correct 7 ms 25436 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 8 ms 25436 KB Output is correct
12 Correct 5 ms 25436 KB Output is correct
13 Correct 34 ms 31572 KB Output is correct
14 Correct 45 ms 32852 KB Output is correct
15 Correct 56 ms 33364 KB Output is correct
16 Correct 56 ms 32080 KB Output is correct
17 Correct 42 ms 33104 KB Output is correct
18 Correct 37 ms 33360 KB Output is correct
19 Correct 44 ms 37204 KB Output is correct
20 Correct 5 ms 25432 KB Output is correct
21 Correct 7 ms 25504 KB Output is correct
22 Correct 49 ms 33360 KB Output is correct
23 Correct 45 ms 31572 KB Output is correct
24 Correct 42 ms 33368 KB Output is correct
25 Correct 32 ms 31836 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25688 KB Output isn't correct
2 Incorrect 7 ms 25436 KB Output isn't correct
3 Correct 39 ms 33348 KB Output is correct
4 Correct 34 ms 32084 KB Output is correct
5 Correct 32 ms 31824 KB Output is correct
6 Correct 113 ms 52820 KB Output is correct
7 Incorrect 7 ms 25436 KB Output isn't correct
8 Incorrect 7 ms 25356 KB Output isn't correct
9 Correct 7 ms 25440 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25416 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 6 ms 25436 KB Output is correct
14 Incorrect 6 ms 25252 KB Output isn't correct
15 Incorrect 9 ms 25436 KB Output isn't correct
16 Incorrect 6 ms 25436 KB Output isn't correct
17 Correct 8 ms 25552 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 7 ms 25524 KB Output is correct
20 Correct 6 ms 25436 KB Output is correct
21 Correct 7 ms 25580 KB Output is correct
22 Incorrect 9 ms 25436 KB Output isn't correct
23 Runtime error 62 ms 72648 KB Execution killed with signal 11
24 Runtime error 69 ms 76108 KB Execution killed with signal 11
25 Correct 39 ms 33364 KB Output is correct
26 Correct 43 ms 32104 KB Output is correct
27 Correct 37 ms 32076 KB Output is correct
28 Correct 38 ms 32348 KB Output is correct
29 Correct 105 ms 47444 KB Output is correct
30 Runtime error 72 ms 74332 KB Execution killed with signal 11
31 Incorrect 52 ms 40136 KB Output isn't correct
32 Runtime error 68 ms 70992 KB Execution killed with signal 11
33 Correct 42 ms 33876 KB Output is correct
34 Correct 36 ms 32080 KB Output is correct
35 Correct 39 ms 32084 KB Output is correct
36 Correct 34 ms 32092 KB Output is correct
37 Correct 113 ms 52952 KB Output is correct
38 Runtime error 74 ms 75068 KB Execution killed with signal 11
39 Runtime error 66 ms 69804 KB Execution killed with signal 11
40 Runtime error 65 ms 75468 KB Execution killed with signal 11
41 Correct 38 ms 33616 KB Output is correct
42 Correct 32 ms 32092 KB Output is correct
43 Correct 34 ms 31992 KB Output is correct
44 Correct 30 ms 31824 KB Output is correct
45 Correct 96 ms 49748 KB Output is correct
46 Runtime error 63 ms 73936 KB Execution killed with signal 11
47 Runtime error 61 ms 75464 KB Execution killed with signal 11
48 Incorrect 45 ms 39996 KB Output isn't correct
49 Correct 36 ms 33372 KB Output is correct
50 Correct 32 ms 32000 KB Output is correct
51 Correct 31 ms 32196 KB Output is correct
52 Correct 31 ms 32088 KB Output is correct
53 Correct 92 ms 49228 KB Output is correct
54 Runtime error 69 ms 73492 KB Execution killed with signal 11