oj.uz

Submission #1077753

# Submission time Handle Problem Language Result Execution time Memory
1077753 2024-08-27T08:54:32 Z SoMotThanhXuan Pipes (BOI13_pipes) C++17
74.0741 / 100
 127 ms 40020 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = b; i >= a; --i)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define REPD(i, a, b) for(int i = b; i > a; -- i)
#define ALL(v) v.begin(),v.end()
#define next __next
#define left __left
#define right __right
#define prev __prev
const int MOD[6] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277, 998244353};
const int BASE[6] = {23309, 300, 330, 280, 2309, 256};
const int base = BASE[0];
const int mod = MOD[0];
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
void minimize(int &u, int v){
    if(u > v) u = v;
}
void maximize(int &u, int v){
    if(u < v) u = v;
}
void minimizell(long long &u, long long v){
    if(u > v) u = v;
}
void maximizell(long long &u, long long v){
    if(u < v) u = v;
}
const int maxN = 1e5 + 2;
const int maxM = 5e5 + 2;
const int maxK = 1e2 + 2;
const int INF = 1e9 + 8;
const long long INFLL = 1e18;
const int LOG = 16;
int N, M;
#define int long long
vector<pair<int, int>> adj[maxN];
pair<int, int> edge[maxM];
int deg[maxN];
bool del[maxN];
queue<int> listSource;
int res[maxM], c[maxN];
int st, ed, firstEdge;
int listEdge[maxN];
int node[maxN];
int cnt = 0;
void Dfs1(int u, int p){
    for(pair<int, int> x : adj[u]){
        int v = x.fi;
        if(v != p){
            Dfs1(v, u);
            res[x.second] = 2 * c[v];
            c[u] -= c[v];
        }
    }
}
void Dfs2(int u, int p, int id){
    node[++cnt] = u;
    listEdge[cnt] = id;
    if(u == ed){
        res[firstEdge] = c[st];
        int d = 1;
        FOR(i, 2, cnt){
            res[firstEdge] += d * c[node[i]];
            d *= -1;
        }
        FOR(i, 2, cnt){
            res[i] = 2 * node[i - 1] - res[i - 1];
        }
        FOR(i, 1, M)cout << res[i] << "\n";
        exit(0);
    }
    for(pair<int, int> x : adj[u]){
        int v = x.fi;
        if(v == p)continue;
        Dfs2(v, u, x.second);
    }
    --cnt;
}
int32_t main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    //freopen(".INP", "w", stdout);
    //freopen(".ANS", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    FOR(i, 1, N)cin >> c[i];
    FOR(i, 1, M){
        int u, v;
        cin >> u >> v;
        edge[i] = make_pair(u, v);
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        deg[u]++;
        deg[v]++;
    }
    if(M > N){
        cout << 0;
        return 0;
    }
    if(M == N - 1){
        Dfs1(1, 0);
        FOR(i, 1, M)cout << res[i] << '\n';
        return 0;
    }
    FOR(i, 1, N)if(deg[i] == 1){
        if(deg[i] == 1){
            listSource.push(i);
            del[i] = true;
        }
    }
    while(!listSource.empty()){
        int u = listSource.front();
        listSource.pop();
        for(pair<int, int> x : adj[u]){

            int v = x.fi;
            if(del[v])continue;
            c[v] -= c[u];
            res[x.se] = 2 * c[u];
            deg[v]--;
            if(deg[v] == 1){
                del[v] = true;
                listSource.push(v);
            }
        }
    }
    int cnt = 0;
    FOR(i, 1, N)if(del[i] == 0)++cnt;
    if((cnt & 1) == 0){
        cout << 0;
        return 0;
    }
    FOR(i, 1, M){
        int u = edge[i].fi, v = edge[i].se;
        if(del[u] == false && del[v] == false){
            st = u;
            firstEdge = i;
            break;
        }
    }
    Dfs2(st, ed, firstEdge);

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 44 ms 12568 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 1 ms 5212 KB Output is correct
13 Correct 28 ms 10700 KB Output is correct
14 Correct 33 ms 11996 KB Output is correct
15 Correct 38 ms 14672 KB Output is correct
16 Correct 35 ms 13148 KB Output is correct
17 Correct 36 ms 14928 KB Output is correct
18 Correct 37 ms 15960 KB Output is correct
19 Correct 40 ms 18588 KB Output is correct
20 Correct 1 ms 7256 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 36 ms 12676 KB Output is correct
23 Correct 27 ms 10580 KB Output is correct
24 Correct 38 ms 14780 KB Output is correct
25 Correct 29 ms 11100 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 18520 KB Output isn't correct
2 Incorrect 5 ms 12380 KB Output isn't correct
3 Correct 27 ms 14048 KB Output is correct
4 Correct 30 ms 14936 KB Output is correct
5 Correct 28 ms 13148 KB Output is correct
6 Correct 117 ms 40020 KB Output is correct
7 Incorrect 9 ms 18520 KB Output isn't correct
8 Incorrect 11 ms 18524 KB Output isn't correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Incorrect 7 ms 10072 KB Output isn't correct
15 Incorrect 7 ms 10328 KB Output isn't correct
16 Incorrect 7 ms 10332 KB Output isn't correct
17 Correct 1 ms 3160 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 1 ms 3160 KB Output is correct
20 Correct 1 ms 3164 KB Output is correct
21 Correct 2 ms 5468 KB Output is correct
22 Incorrect 5 ms 10172 KB Output isn't correct
23 Incorrect 41 ms 18996 KB Output isn't correct
24 Incorrect 58 ms 22868 KB Output isn't correct
25 Correct 32 ms 13916 KB Output is correct
26 Correct 30 ms 13548 KB Output is correct
27 Correct 29 ms 13376 KB Output is correct
28 Correct 35 ms 13764 KB Output is correct
29 Correct 96 ms 33620 KB Output is correct
30 Incorrect 60 ms 21072 KB Output isn't correct
31 Incorrect 56 ms 25568 KB Output isn't correct
32 Incorrect 89 ms 25680 KB Output isn't correct
33 Correct 71 ms 12216 KB Output is correct
34 Correct 34 ms 11088 KB Output is correct
35 Correct 31 ms 11096 KB Output is correct
36 Correct 35 ms 11056 KB Output is correct
37 Correct 125 ms 37972 KB Output is correct
38 Incorrect 49 ms 20304 KB Output isn't correct
39 Incorrect 77 ms 25424 KB Output isn't correct
40 Incorrect 62 ms 27492 KB Output isn't correct
41 Correct 29 ms 11868 KB Output is correct
42 Correct 27 ms 13400 KB Output is correct
43 Correct 32 ms 13496 KB Output is correct
44 Correct 30 ms 13124 KB Output is correct
45 Correct 108 ms 34652 KB Output is correct
46 Incorrect 65 ms 20372 KB Output isn't correct
47 Incorrect 62 ms 29760 KB Output isn't correct
48 Incorrect 65 ms 24124 KB Output isn't correct
49 Correct 39 ms 13816 KB Output is correct
50 Correct 31 ms 13408 KB Output is correct
51 Correct 28 ms 11428 KB Output is correct
52 Correct 33 ms 13332 KB Output is correct
53 Correct 127 ms 36040 KB Output is correct
54 Incorrect 60 ms 20352 KB Output isn't correct