oj.uz

Submission #490306

# Submission time Handle Problem Language Result Execution time Memory
490306 2021-11-26T20:31:14 Z JerryLiu06 Pipes (BOI13_pipes) C++17
74.0741 / 100
 79 ms 11844 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];
            
            adj[Y.f].erase(find(all(adj[Y.f]), pi{cur, 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];
    }
    cout << sum << "\n";
    
    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 52 ms 9060 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2572 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 1 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 41 ms 7684 KB Output is correct
14 Correct 51 ms 8684 KB Output is correct
15 Correct 51 ms 9052 KB Output is correct
16 Correct 42 ms 8132 KB Output is correct
17 Correct 56 ms 9040 KB Output is correct
18 Correct 59 ms 8992 KB Output is correct
19 Correct 47 ms 8324 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 51 ms 9068 KB Output is correct
23 Correct 38 ms 7660 KB Output is correct
24 Correct 52 ms 9096 KB Output is correct
25 Correct 40 ms 7948 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Correct 46 ms 8568 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 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 Correct 1 ms 2636 KB Output is 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 2764 KB Output isn't correct
16 Incorrect 2 ms 2636 KB Output isn't correct
17 Correct 1 ms 2636 KB Output is 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 2636 KB Output is correct
22 Incorrect 2 ms 2764 KB Output isn't correct
23 Incorrect 45 ms 9612 KB Output isn't correct
24 Incorrect 53 ms 10784 KB Output isn't correct
25 Correct 40 ms 8524 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 2 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 64 ms 10044 KB Output isn't correct
31 Incorrect 53 ms 11844 KB Output isn't correct
32 Incorrect 56 ms 9660 KB Output isn't correct
33 Correct 46 ms 8732 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 57 ms 10332 KB Output isn't correct
39 Incorrect 52 ms 9392 KB Output isn't correct
40 Incorrect 52 ms 10712 KB Output isn't correct
41 Correct 41 ms 8820 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 51 ms 10132 KB Output isn't correct
47 Incorrect 69 ms 10744 KB Output isn't correct
48 Incorrect 79 ms 11764 KB Output isn't correct
49 Correct 42 ms 8308 KB Output is correct
50 Correct 1 ms 2644 KB Output is correct
51 Correct 1 ms 2636 KB Output is correct
52 Correct 1 ms 2636 KB Output is correct
53 Correct 2 ms 2636 KB Output is correct
54 Incorrect 50 ms 9960 KB Output isn't correct