oj.uz

Submission #860744

# Submission time Handle Problem Language Result Execution time Memory
860744 2023-10-14T06:25:26 Z Ellinor Pipes (BOI13_pipes) C++14
30 / 100
 643 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int N, M; //
vector<int> net;

//
vector<vector<pii>> graph; // tree 30p

vector<int> ans;


ll dfs(int node, int par, int kant) // kant ?
{
    ll c = 0;
    rep(i,0,graph[node].size()) {
        if (graph[node][i].first != par) {
            c += dfs(graph[node][i].first, node, graph[node][i].second);
        }
    }
    if (kant != -1)
    {
        return ans[kant] = net[node] - c;
    }
    return 0;
}


int32_t main()
{
    fast();
    cin >> N >> M;
    net.assign(N, 0);
    rep(i,0,N) {
        cin >> net[i];
    }
    graph.assign(N, {});
    int a, b;
    rep(i,0,M) {
        cin >> a >> b;
        a--; b--; //
        graph[a].pb({b, i});
        graph[b].pb({a, i});
    }

    ans.assign(M, -1);
    dfs(1, -1, -1);
    rep(i,0,M) {
        // not tree, can know ?
        cout << ans[i] * 2 << "\n";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 36 ms 9920 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 28 ms 8068 KB Output is correct
14 Correct 33 ms 9472 KB Output is correct
15 Correct 36 ms 10040 KB Output is correct
16 Correct 30 ms 8532 KB Output is correct
17 Correct 37 ms 10072 KB Output is correct
18 Correct 35 ms 10056 KB Output is correct
19 Correct 38 ms 12632 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 35 ms 9956 KB Output is correct
23 Correct 28 ms 8028 KB Output is correct
24 Correct 37 ms 10064 KB Output is correct
25 Correct 32 ms 8484 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 131072 KB Execution killed with signal 9
2 Runtime error 99 ms 131072 KB Execution killed with signal 9
3 Runtime error 276 ms 131072 KB Execution killed with signal 9
4 Runtime error 193 ms 131072 KB Execution killed with signal 9
5 Runtime error 141 ms 131072 KB Execution killed with signal 9
6 Runtime error 203 ms 131072 KB Execution killed with signal 9
7 Runtime error 91 ms 131072 KB Execution killed with signal 9
8 Runtime error 124 ms 131072 KB Execution killed with signal 9
9 Runtime error 87 ms 131072 KB Execution killed with signal 9
10 Runtime error 80 ms 131072 KB Execution killed with signal 9
11 Runtime error 81 ms 131072 KB Execution killed with signal 9
12 Runtime error 82 ms 131072 KB Execution killed with signal 9
13 Runtime error 81 ms 131072 KB Execution killed with signal 9
14 Runtime error 90 ms 131072 KB Execution killed with signal 9
15 Runtime error 100 ms 131072 KB Execution killed with signal 9
16 Runtime error 111 ms 131072 KB Execution killed with signal 9
17 Runtime error 106 ms 131072 KB Execution killed with signal 9
18 Runtime error 110 ms 131072 KB Execution killed with signal 9
19 Runtime error 98 ms 131072 KB Execution killed with signal 9
20 Runtime error 80 ms 131072 KB Execution killed with signal 9
21 Runtime error 82 ms 131072 KB Execution killed with signal 9
22 Runtime error 98 ms 131072 KB Execution killed with signal 9
23 Runtime error 205 ms 131072 KB Execution killed with signal 9
24 Runtime error 274 ms 131072 KB Execution killed with signal 9
25 Runtime error 255 ms 131072 KB Execution killed with signal 9
26 Runtime error 205 ms 131072 KB Execution killed with signal 9
27 Runtime error 193 ms 131072 KB Execution killed with signal 9
28 Runtime error 108 ms 131072 KB Execution killed with signal 9
29 Runtime error 173 ms 131072 KB Execution killed with signal 9
30 Runtime error 336 ms 131072 KB Execution killed with signal 9
31 Runtime error 220 ms 131072 KB Execution killed with signal 9
32 Runtime error 460 ms 131072 KB Execution killed with signal 9
33 Runtime error 209 ms 131072 KB Execution killed with signal 9
34 Runtime error 201 ms 131072 KB Execution killed with signal 9
35 Runtime error 205 ms 131072 KB Execution killed with signal 9
36 Runtime error 107 ms 131072 KB Execution killed with signal 9
37 Runtime error 192 ms 131072 KB Execution killed with signal 9
38 Runtime error 239 ms 131072 KB Execution killed with signal 9
39 Runtime error 643 ms 131072 KB Execution killed with signal 9
40 Runtime error 215 ms 131072 KB Execution killed with signal 9
41 Runtime error 206 ms 131072 KB Execution killed with signal 9
42 Runtime error 190 ms 131072 KB Execution killed with signal 9
43 Runtime error 186 ms 131072 KB Execution killed with signal 9
44 Runtime error 145 ms 131072 KB Execution killed with signal 9
45 Runtime error 170 ms 131072 KB Execution killed with signal 9
46 Runtime error 379 ms 131072 KB Execution killed with signal 9
47 Runtime error 198 ms 131072 KB Execution killed with signal 9
48 Runtime error 198 ms 131072 KB Execution killed with signal 9
49 Runtime error 478 ms 131072 KB Execution killed with signal 9
50 Runtime error 222 ms 131072 KB Execution killed with signal 9
51 Runtime error 254 ms 131072 KB Execution killed with signal 9
52 Runtime error 199 ms 131072 KB Execution killed with signal 9
53 Runtime error 165 ms 131072 KB Execution killed with signal 9
54 Runtime error 219 ms 131072 KB Execution killed with signal 9