oj.uz

Submission #1077737

# Submission time Handle Problem Language Result Execution time Memory
1077737 2024-08-27T08:49:03 Z TVSown Pipes (BOI13_pipes) C++17
74.0741 / 100
 120 ms 52944 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(j, 0, szz(st) - 2){
            int u = st[j];
            for(auto [v, i] : e[u]){
                if(v == st[j + 1]){
//                    cout << u << " " << st[j + 1] << " " << A - B << " " << B - A << "\n";
                    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(j, 0, szz(st) - 2){
      |             ~~~~~~~~~~~~~~~~~          
pipes.cpp:90:9: note: in expansion of macro 'FOR'
   90 |         FOR(j, 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:123:5: note: in expansion of macro 'inp'
  123 |     inp("in.txt");
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25436 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 42 ms 33156 KB Output is correct
5 Correct 8 ms 25432 KB Output is correct
6 Correct 7 ms 25288 KB Output is correct
7 Correct 8 ms 25432 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 9 ms 25436 KB Output is correct
10 Correct 7 ms 25436 KB Output is correct
11 Correct 8 ms 25432 KB Output is correct
12 Correct 9 ms 25436 KB Output is correct
13 Correct 40 ms 31692 KB Output is correct
14 Correct 40 ms 32852 KB Output is correct
15 Correct 50 ms 33132 KB Output is correct
16 Correct 36 ms 32152 KB Output is correct
17 Correct 41 ms 33104 KB Output is correct
18 Correct 48 ms 33372 KB Output is correct
19 Correct 49 ms 37068 KB Output is correct
20 Correct 7 ms 25432 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct
22 Correct 41 ms 33176 KB Output is correct
23 Correct 32 ms 31576 KB Output is correct
24 Correct 40 ms 33364 KB Output is correct
25 Correct 38 ms 31828 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 25692 KB Output isn't correct
2 Incorrect 8 ms 25436 KB Output isn't correct
3 Correct 44 ms 33372 KB Output is correct
4 Correct 40 ms 32160 KB Output is correct
5 Correct 32 ms 31836 KB Output is correct
6 Correct 116 ms 52944 KB Output is correct
7 Incorrect 8 ms 25436 KB Output isn't correct
8 Incorrect 9 ms 25360 KB Output isn't correct
9 Correct 7 ms 25456 KB Output is correct
10 Correct 8 ms 25280 KB Output is correct
11 Correct 9 ms 25436 KB Output is correct
12 Correct 6 ms 25436 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Incorrect 8 ms 25436 KB Output isn't correct
15 Incorrect 8 ms 25436 KB Output isn't correct
16 Incorrect 9 ms 25432 KB Output isn't correct
17 Correct 8 ms 25436 KB Output is correct
18 Correct 8 ms 25436 KB Output is correct
19 Correct 8 ms 25436 KB Output is correct
20 Correct 8 ms 25436 KB Output is correct
21 Correct 8 ms 25436 KB Output is correct
22 Incorrect 10 ms 25420 KB Output isn't correct
23 Incorrect 49 ms 36812 KB Output isn't correct
24 Incorrect 59 ms 38776 KB Output isn't correct
25 Correct 36 ms 33372 KB Output is correct
26 Correct 34 ms 32084 KB Output is correct
27 Correct 36 ms 31856 KB Output is correct
28 Correct 35 ms 32340 KB Output is correct
29 Correct 97 ms 47412 KB Output is correct
30 Incorrect 53 ms 37596 KB Output isn't correct
31 Incorrect 64 ms 41412 KB Output isn't correct
32 Incorrect 46 ms 35612 KB Output isn't correct
33 Correct 40 ms 33876 KB Output is correct
34 Correct 37 ms 32208 KB Output is correct
35 Correct 35 ms 32092 KB Output is correct
36 Correct 37 ms 32084 KB Output is correct
37 Correct 120 ms 52736 KB Output is correct
38 Incorrect 60 ms 38088 KB Output isn't correct
39 Incorrect 50 ms 35084 KB Output isn't correct
40 Incorrect 59 ms 38348 KB Output isn't correct
41 Correct 39 ms 33616 KB Output is correct
42 Correct 36 ms 32088 KB Output is correct
43 Correct 35 ms 32080 KB Output is correct
44 Correct 35 ms 31824 KB Output is correct
45 Correct 102 ms 49716 KB Output is correct
46 Incorrect 59 ms 37436 KB Output isn't correct
47 Incorrect 59 ms 38344 KB Output isn't correct
48 Incorrect 62 ms 41156 KB Output isn't correct
49 Correct 41 ms 33364 KB Output is correct
50 Correct 34 ms 31992 KB Output is correct
51 Correct 46 ms 32180 KB Output is correct
52 Correct 34 ms 32084 KB Output is correct
53 Correct 100 ms 49140 KB Output is correct
54 Incorrect 52 ms 37132 KB Output isn't correct