oj.uz

Submission #1077728

# Submission time Handle Problem Language Result Execution time Memory
1077728 2024-08-27T08:44:50 Z TVSown Pipes (BOI13_pipes) C++17
74.0741 / 100
 126 ms 76620 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 << " " << c[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);
        cout << A << " " << B << "\n";
        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)
......
   90 |         FOR(i, 0, szz(st) - 2){
      |             ~~~~~~~~~~~~~~~~~          
pipes.cpp:90:9: note: in expansion of macro 'FOR'
   90 |         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:122:5: note: in expansion of macro 'inp'
  122 |     inp("in.txt");
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 53 ms 33336 KB Output is correct
5 Correct 5 ms 25432 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25432 KB Output is correct
9 Correct 7 ms 25436 KB Output is correct
10 Correct 6 ms 25416 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 7 ms 25436 KB Output is correct
13 Correct 34 ms 31660 KB Output is correct
14 Correct 37 ms 32852 KB Output is correct
15 Correct 41 ms 33360 KB Output is correct
16 Correct 36 ms 31976 KB Output is correct
17 Correct 41 ms 33108 KB Output is correct
18 Correct 49 ms 33364 KB Output is correct
19 Correct 51 ms 37200 KB Output is correct
20 Correct 5 ms 25432 KB Output is correct
21 Correct 9 ms 25432 KB Output is correct
22 Correct 42 ms 33368 KB Output is correct
23 Correct 35 ms 31604 KB Output is correct
24 Correct 51 ms 33364 KB Output is correct
25 Correct 34 ms 31820 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 25436 KB Output isn't correct
2 Incorrect 6 ms 25436 KB Output isn't correct
3 Correct 38 ms 33516 KB Output is correct
4 Correct 36 ms 32084 KB Output is correct
5 Correct 35 ms 31824 KB Output is correct
6 Correct 126 ms 52820 KB Output is correct
7 Incorrect 6 ms 25436 KB Output isn't correct
8 Incorrect 6 ms 25436 KB Output isn't correct
9 Correct 6 ms 25436 KB Output is correct
10 Correct 7 ms 25404 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 5 ms 25436 KB Output is correct
13 Correct 5 ms 25432 KB Output is correct
14 Incorrect 7 ms 25436 KB Output isn't correct
15 Incorrect 7 ms 25524 KB Output isn't correct
16 Incorrect 6 ms 25456 KB Output isn't correct
17 Correct 7 ms 25436 KB Output is correct
18 Correct 6 ms 25436 KB Output is correct
19 Correct 6 ms 25436 KB Output is correct
20 Correct 6 ms 25436 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct
22 Incorrect 6 ms 25436 KB Output isn't correct
23 Runtime error 80 ms 73168 KB Execution killed with signal 11
24 Runtime error 77 ms 76620 KB Execution killed with signal 11
25 Correct 39 ms 33392 KB Output is correct
26 Correct 32 ms 32088 KB Output is correct
27 Correct 35 ms 32084 KB Output is correct
28 Correct 35 ms 32336 KB Output is correct
29 Correct 100 ms 47472 KB Output is correct
30 Runtime error 77 ms 74720 KB Execution killed with signal 11
31 Incorrect 67 ms 41164 KB Output isn't correct
32 Runtime error 71 ms 71076 KB Execution killed with signal 11
33 Correct 39 ms 33756 KB Output is correct
34 Correct 37 ms 32080 KB Output is correct
35 Correct 38 ms 32092 KB Output is correct
36 Correct 36 ms 32180 KB Output is correct
37 Correct 123 ms 52816 KB Output is correct
38 Runtime error 71 ms 75376 KB Execution killed with signal 11
39 Runtime error 64 ms 70040 KB Execution killed with signal 11
40 Runtime error 82 ms 75972 KB Execution killed with signal 11
41 Correct 36 ms 33624 KB Output is correct
42 Correct 37 ms 32080 KB Output is correct
43 Correct 35 ms 32080 KB Output is correct
44 Correct 31 ms 31836 KB Output is correct
45 Correct 111 ms 49860 KB Output is correct
46 Runtime error 78 ms 74400 KB Execution killed with signal 11
47 Runtime error 76 ms 76084 KB Execution killed with signal 11
48 Incorrect 60 ms 40796 KB Output isn't correct
49 Correct 40 ms 33356 KB Output is correct
50 Correct 39 ms 32052 KB Output is correct
51 Correct 37 ms 32084 KB Output is correct
52 Correct 37 ms 32080 KB Output is correct
53 Correct 100 ms 49360 KB Output is correct
54 Runtime error 82 ms 73996 KB Execution killed with signal 11