oj.uz

Submission #659225

# Submission time Handle Problem Language Result Execution time Memory
659225 2022-11-17T04:50:52 Z Soul234 Pipes (BOI13_pipes) C++14
87.037 / 100
 165 ms 35384 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;

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((tin[v]-tin[u])&1) {
                cout << "0\n";
                exit(0);
            }
        }
        else {
            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 90 ms 21788 KB Output is correct
5 Correct 9 ms 12500 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 7 ms 12500 KB Output is correct
8 Correct 6 ms 12500 KB Output is correct
9 Correct 8 ms 12572 KB Output is correct
10 Correct 7 ms 12592 KB Output is correct
11 Correct 7 ms 12628 KB Output is correct
12 Correct 7 ms 12628 KB Output is correct
13 Correct 55 ms 19864 KB Output is correct
14 Correct 74 ms 21292 KB Output is correct
15 Correct 78 ms 21816 KB Output is correct
16 Correct 66 ms 20412 KB Output is correct
17 Correct 82 ms 21836 KB Output is correct
18 Correct 80 ms 21884 KB Output is correct
19 Correct 88 ms 23904 KB Output is correct
20 Correct 7 ms 12500 KB Output is correct
21 Correct 8 ms 12628 KB Output is correct
22 Correct 93 ms 21780 KB Output is correct
23 Correct 56 ms 19892 KB Output is correct
24 Correct 80 ms 21896 KB Output is correct
25 Correct 58 ms 20300 KB Output is correct

Subtask #2
57.037037037 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12044 KB Output isn't correct
2 Incorrect 7 ms 12236 KB Output isn't correct
3 Correct 55 ms 21888 KB Output is correct
4 Correct 45 ms 18420 KB Output is correct
5 Correct 43 ms 18548 KB Output is correct
6 Correct 165 ms 35212 KB Output is correct
7 Incorrect 7 ms 12116 KB Output isn't correct
8 Correct 7 ms 12564 KB Output is correct
9 Correct 6 ms 12012 KB Output is correct
10 Correct 6 ms 12016 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 7 ms 12100 KB Output is correct
14 Correct 7 ms 12604 KB Output is correct
15 Incorrect 7 ms 12116 KB Output isn't correct
16 Correct 7 ms 12628 KB Output is correct
17 Correct 7 ms 12116 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 7 ms 12160 KB Output is correct
22 Correct 7 ms 12628 KB Output is correct
23 Correct 67 ms 24668 KB Output is correct
24 Incorrect 56 ms 22744 KB Output isn't correct
25 Correct 52 ms 21888 KB Output is correct
26 Correct 48 ms 18404 KB Output is correct
27 Correct 44 ms 18276 KB Output is correct
28 Correct 49 ms 18924 KB Output is correct
29 Correct 132 ms 31068 KB Output is correct
30 Incorrect 59 ms 24548 KB Output isn't correct
31 Correct 93 ms 29416 KB Output is correct
32 Correct 83 ms 23344 KB Output is correct
33 Incorrect 104 ms 26660 KB Output isn't correct
34 Correct 50 ms 18376 KB Output is correct
35 Correct 44 ms 18408 KB Output is correct
36 Correct 45 ms 18708 KB Output is correct
37 Correct 159 ms 35384 KB Output is correct
38 Correct 91 ms 26700 KB Output is correct
39 Correct 77 ms 22808 KB Output is correct
40 Incorrect 57 ms 22564 KB Output isn't correct
41 Incorrect 101 ms 29440 KB Output isn't correct
42 Correct 50 ms 18280 KB Output is correct
43 Correct 42 ms 18332 KB Output is correct
44 Correct 43 ms 18520 KB Output is correct
45 Correct 121 ms 32124 KB Output is correct
46 Incorrect 63 ms 25184 KB Output isn't correct
47 Correct 82 ms 26192 KB Output is correct
48 Correct 100 ms 29104 KB Output is correct
49 Correct 50 ms 20180 KB Output is correct
50 Correct 43 ms 18552 KB Output is correct
51 Correct 42 ms 18604 KB Output is correct
52 Correct 42 ms 18396 KB Output is correct
53 Correct 138 ms 32296 KB Output is correct
54 Correct 93 ms 25916 KB Output is correct