oj.uz

Submission #490287

# Submission time Handle Problem Language Result Execution time Memory
490287 2021-11-26T19:03:44 Z JerryLiu06 Pipes (BOI13_pipes) C++17
67.5926 / 100
 57 ms 10464 KB 
// https://oj.uz/problem/view/BOI13_pipes
 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
#define FASTIOF ios_base::sync_with_stdio(false); fin.tie(0);
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

int N, M; ll C[MX]; vpi adj[MX]; bool inCyc[MX]; int inDeg[MX]; ll ans[MX];

int main() {
    FASTIO;

    cin >> N >> M;

    if (M > N) {
        return cout << "0", 0;
    }
    FOR(i, 1, N + 1) {
        cin >> C[i];
    }
    FOR(i, 1, M + 1) {
        int A, B; cin >> A >> B;

        adj[A].pb({B, i});
        adj[B].pb({A, i});

        inDeg[A]++;
        inDeg[B]++;
    }
    FOR(i, 1, N + 1) inCyc[i] = true;

    queue<int> Q;

    FOR(i, 1, N + 1) {
        if (inDeg[i] == 1) {
            Q.push(i);
        }
    }
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();

        inCyc[cur] = false;
        
        EACH(Y, adj[cur]) {
            if (!inCyc[Y.f]) continue;

            ans[Y.s] = C[cur];

            inDeg[Y.f]--;
            C[Y.f] -= ans[Y.s];

            if (inDeg[Y.f] == 1) {
                Q.push(Y.f);
            }
        }
    }
   // cout << ans[11] << "HI " << "\n";
    if (M == N - 1) {
        FOR(i, 1, M + 1) {
            cout << 2 * ans[i] << "\n";
        }
        return 0;
    }
    vi cyc, edges; int curNode = -1;

    FOR(i, 1, N + 1) {
        if (inCyc[i]) {
            curNode = i; 
            edges.pb(adj[i][0].s);
            break;
        }
    }
    while (inCyc[curNode]) {
        inCyc[curNode] = false;

        cyc.pb(curNode);

        EACH(Y, adj[curNode]) {
            if (Y.s != edges.bk) {
                curNode = Y.f;
                edges.pb(Y.s);
                break;
            }
        }
    }
    edges.pop_back();

    N = sz(cyc);
    
    if (N % 2 == 0) {
        return cout << "0", 0;
    }
    ll sum = 0;
    
    EACH(i, cyc) {
        sum += C[i];
    }
    sum /= 2;
    
    vpi newCyc; int ind = 0;

    while (sz(newCyc) < N) {
        newCyc.pb({cyc[ind], ind});

        ind = (ind + 2) % N;
    }
    F0R(i, N) {
        newCyc.pb(newCyc[i]);
    }
    vl pref(sz(newCyc) + 1, 0);

    FOR(i, 1, sz(newCyc) + 1) {
        pref[i] = pref[i - 1] + C[newCyc[i - 1].f];
    }
    int numForward = (N - 1) / 2;

    F0R(i, N) {
        int curEdge = edges[(newCyc[i].s + N - 1) % N];
        
        ans[curEdge] = sum - (pref[i + numForward] - pref[i]);
    }
    FOR(i, 1, M + 1) {
        cout << 2 * ans[i] << "\n";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 49 ms 9024 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 39 ms 7784 KB Output is correct
14 Correct 48 ms 8668 KB Output is correct
15 Correct 51 ms 9120 KB Output is correct
16 Correct 46 ms 8156 KB Output is correct
17 Correct 48 ms 9028 KB Output is correct
18 Correct 48 ms 9100 KB Output is correct
19 Correct 48 ms 8340 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 52 ms 9056 KB Output is correct
23 Correct 40 ms 7692 KB Output is correct
24 Correct 50 ms 9060 KB Output is correct
25 Correct 39 ms 8012 KB Output is correct

Subtask #2
37.5925925926 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2636 KB Output isn't correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Incorrect 44 ms 8324 KB Output isn't correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 1 ms 2636 KB Output isn't correct
9 Incorrect 1 ms 2636 KB Output isn't correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 1 ms 2636 KB Output is correct
12 Correct 1 ms 2636 KB Output is correct
13 Correct 1 ms 2636 KB Output is correct
14 Incorrect 1 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2636 KB Output isn't correct
16 Incorrect 2 ms 2636 KB Output isn't correct
17 Incorrect 2 ms 2636 KB Output isn't correct
18 Correct 1 ms 2636 KB Output is correct
19 Correct 1 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 31 ms 7184 KB Output isn't correct
24 Incorrect 52 ms 10056 KB Output isn't correct
25 Incorrect 42 ms 8304 KB Output isn't correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 1 ms 2636 KB Output is correct
28 Correct 1 ms 2636 KB Output is correct
29 Correct 1 ms 2636 KB Output is correct
30 Incorrect 40 ms 7772 KB Output isn't correct
31 Incorrect 41 ms 8196 KB Output isn't correct
32 Incorrect 45 ms 8524 KB Output isn't correct
33 Correct 40 ms 8464 KB Output is correct
34 Correct 1 ms 2636 KB Output is correct
35 Correct 1 ms 2636 KB Output is correct
36 Correct 1 ms 2636 KB Output is correct
37 Correct 1 ms 2636 KB Output is correct
38 Incorrect 47 ms 8932 KB Output isn't correct
39 Incorrect 48 ms 8956 KB Output isn't correct
40 Incorrect 51 ms 10464 KB Output isn't correct
41 Correct 35 ms 7876 KB Output is correct
42 Correct 1 ms 2636 KB Output is correct
43 Correct 1 ms 2636 KB Output is correct
44 Correct 1 ms 2636 KB Output is correct
45 Correct 1 ms 2636 KB Output is correct
46 Incorrect 46 ms 8180 KB Output isn't correct
47 Incorrect 57 ms 9816 KB Output isn't correct
48 Incorrect 44 ms 8240 KB Output isn't correct
49 Incorrect 45 ms 8556 KB Output isn't correct
50 Correct 2 ms 2636 KB Output is correct
51 Correct 1 ms 2636 KB Output is correct
52 Correct 1 ms 2636 KB Output is correct
53 Correct 1 ms 2636 KB Output is correct
54 Incorrect 47 ms 8248 KB Output isn't correct