oj.uz

Submission #659226

# Submission time Handle Problem Language Result Execution time Memory
659226 2022-11-17T04:52:29 Z Soul234 Pipes (BOI13_pipes) C++14
100 / 100
 184 ms 35276 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#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(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second
#define int long long

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 5e5+5;

int N, M;

vi adj[MX];

int tin[MX], tt, dep[MX];

int deg[MX], val[MX];

pi eds[MX];
bool used[MX], vis[MX];

int ans[MX];

void dfs(int u, int p) {
    tin[u] = ++tt;
    each(id, adj[u]) if(!used[id]) {
        used[id] = true;
        int v = eds[id].fi ^ eds[id].se ^ u;
        if(tin[v]) {
            if((dep[v]-dep[u])&1) {
                cout << "0\n";
                exit(0);
            }
        }
        else {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }
}

vi lst, lstid;

ll sum = 0;

int src;

void dfsList(int u, int p) {
    lst.pb(u);
    vis[u] = 1;
    sum += val[u];
    each(id, adj[u]) {
        int v = u ^ eds[id].fi ^ eds[id].se;
        if(deg[v] == 2 && v != p) {
            if(!vis[v] || v == src) lstid.pb(id);
        }
        if(!vis[v] && deg[v] == 2) {
            dfsList(v, u);
            return;
        }
    }
}

void solve() {
    cin >> N >> M;
    FOR(i,1,N+1) cin >> val[i];
    F0R(i, M) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(i);
        adj[v].pb(i);
        eds[i] = {u, v};
        deg[u]++;
        deg[v]++;
    }
    if(M > N) {
        cout << "0\n";
        return;
    }
    dfs(1, -1);
    queue<int> q;
    FOR(i,1,N+1) if(deg[i] == 1) {
        q.push(i);
    }
    memset(used, false, sizeof used);
    while(sz(q)) {
        int u = q.front(); q.pop();
        each(id, adj[u]) if(!used[id]) {
            used[id] = true;
            int v = eds[id].fi ^ eds[id].se ^ u;
            val[v] -= val[u];
            ans[id] = val[u];
            if(--deg[v] == 1) {
                q.push(v);
            }
        }
    }
    FOR(i,1,N+1) if(deg[i] == 2) {
        src = i;
        dfsList(i, -1);
        break;
    }
    sum /= 2;
    if(!lstid.empty()) {
        for(int i = 2; i<sz(lst); i += 2) {
            sum -= val[lst[i]];
        }
//        each(id, lstid) dbg(id);
//        dbg(sum);
        ans[lstid[0]] = sum;
        for(int i = 1; i<sz(lstid); i++) {
            ans[lstid[i]] = val[lst[i]] - ans[lstid[i-1]];
        }
    }
    F0R(i, M) {
        cout << 2*ans[i] << nl;
    }
}

signed main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

pipes.cpp: In function 'void setIO(std::string)':
pipes.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 7 ms 12628 KB Output is correct
4 Correct 80 ms 22524 KB Output is correct
5 Correct 6 ms 12500 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 7 ms 12500 KB Output is correct
8 Correct 7 ms 12596 KB Output is correct
9 Correct 7 ms 12628 KB Output is correct
10 Correct 7 ms 12668 KB Output is correct
11 Correct 7 ms 12600 KB Output is correct
12 Correct 7 ms 12616 KB Output is correct
13 Correct 61 ms 20504 KB Output is correct
14 Correct 71 ms 22036 KB Output is correct
15 Correct 80 ms 22636 KB Output is correct
16 Correct 69 ms 21128 KB Output is correct
17 Correct 82 ms 22704 KB Output is correct
18 Correct 85 ms 22656 KB Output is correct
19 Correct 87 ms 24780 KB Output is correct
20 Correct 7 ms 12516 KB Output is correct
21 Correct 7 ms 12692 KB Output is correct
22 Correct 86 ms 22656 KB Output is correct
23 Correct 59 ms 20516 KB Output is correct
24 Correct 81 ms 22732 KB Output is correct
25 Correct 62 ms 20916 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 64 ms 22612 KB Output is correct
4 Correct 48 ms 18396 KB Output is correct
5 Correct 45 ms 18552 KB Output is correct
6 Correct 168 ms 35276 KB Output is correct
7 Correct 7 ms 12500 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 8 ms 12116 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 12500 KB Output is correct
15 Correct 7 ms 12740 KB Output is correct
16 Correct 7 ms 12744 KB Output is correct
17 Correct 7 ms 12112 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 6 ms 12116 KB Output is correct
21 Correct 7 ms 12244 KB Output is correct
22 Correct 7 ms 12756 KB Output is correct
23 Correct 77 ms 25260 KB Output is correct
24 Correct 89 ms 27200 KB Output is correct
25 Correct 54 ms 22604 KB Output is correct
26 Correct 46 ms 18472 KB Output is correct
27 Correct 42 ms 18248 KB Output is correct
28 Correct 49 ms 18836 KB Output is correct
29 Correct 138 ms 31104 KB Output is correct
30 Correct 95 ms 27868 KB Output is correct
31 Correct 90 ms 30172 KB Output is correct
32 Correct 82 ms 24132 KB Output is correct
33 Correct 56 ms 23632 KB Output is correct
34 Correct 47 ms 18420 KB Output is correct
35 Correct 44 ms 18380 KB Output is correct
36 Correct 46 ms 18656 KB Output is correct
37 Correct 184 ms 35240 KB Output is correct
38 Correct 88 ms 27452 KB Output is correct
39 Correct 82 ms 23628 KB Output is correct
40 Correct 83 ms 26852 KB Output is correct
41 Correct 61 ms 25528 KB Output is correct
42 Correct 43 ms 18296 KB Output is correct
43 Correct 43 ms 18260 KB Output is correct
44 Correct 43 ms 18616 KB Output is correct
45 Correct 126 ms 32100 KB Output is correct
46 Correct 93 ms 28584 KB Output is correct
47 Correct 88 ms 27044 KB Output is correct
48 Correct 90 ms 29888 KB Output is correct
49 Correct 51 ms 20856 KB Output is correct
50 Correct 43 ms 18516 KB Output is correct
51 Correct 43 ms 18612 KB Output is correct
52 Correct 46 ms 18492 KB Output is correct
53 Correct 140 ms 32192 KB Output is correct
54 Correct 91 ms 26752 KB Output is correct