oj.uz

Submission #1077752

# Submission time Handle Problem Language Result Execution time Memory
1077752 2024-08-27T08:53:36 Z SoMotThanhXuan Pipes (BOI13_pipes) C++17
74.0741 / 100
 117 ms 24656 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;
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;
}
int 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 3932 KB Output is correct
2 Correct 2 ms 4012 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 52 ms 12352 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 5980 KB Output is correct
13 Correct 27 ms 10688 KB Output is correct
14 Correct 34 ms 10580 KB Output is correct
15 Correct 38 ms 11084 KB Output is correct
16 Correct 37 ms 11092 KB Output is correct
17 Correct 33 ms 12104 KB Output is correct
18 Correct 39 ms 11092 KB Output is correct
19 Correct 38 ms 14444 KB Output is correct
20 Correct 1 ms 3932 KB Output is correct
21 Correct 1 ms 3932 KB Output is correct
22 Correct 36 ms 11084 KB Output is correct
23 Correct 27 ms 9552 KB Output is correct
24 Correct 33 ms 11084 KB Output is correct
25 Correct 28 ms 10064 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 15196 KB Output isn't correct
2 Incorrect 5 ms 9820 KB Output isn't correct
3 Correct 26 ms 10408 KB Output is correct
4 Correct 26 ms 10840 KB Output is correct
5 Correct 42 ms 9980 KB Output is correct
6 Correct 106 ms 24472 KB Output is correct
7 Incorrect 9 ms 17288 KB Output isn't correct
8 Incorrect 10 ms 17244 KB Output isn't correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 5976 KB Output is correct
13 Correct 1 ms 3932 KB Output is correct
14 Incorrect 4 ms 9728 KB Output isn't correct
15 Incorrect 5 ms 11868 KB Output isn't correct
16 Incorrect 5 ms 11992 KB Output isn't correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 2 ms 3932 KB Output is correct
20 Correct 1 ms 3932 KB Output is correct
21 Correct 2 ms 5980 KB Output is correct
22 Incorrect 5 ms 11868 KB Output isn't correct
23 Incorrect 42 ms 16444 KB Output isn't correct
24 Incorrect 49 ms 19008 KB Output isn't correct
25 Correct 31 ms 10324 KB Output is correct
26 Correct 28 ms 9720 KB Output is correct
27 Correct 24 ms 10576 KB Output is correct
28 Correct 27 ms 10068 KB Output is correct
29 Correct 94 ms 21332 KB Output is correct
30 Incorrect 42 ms 17236 KB Output isn't correct
31 Incorrect 47 ms 20564 KB Output isn't correct
32 Incorrect 71 ms 23120 KB Output isn't correct
33 Correct 32 ms 11396 KB Output is correct
34 Correct 34 ms 9816 KB Output is correct
35 Correct 27 ms 9812 KB Output is correct
36 Correct 36 ms 9896 KB Output is correct
37 Correct 117 ms 24656 KB Output is correct
38 Incorrect 44 ms 18512 KB Output isn't correct
39 Incorrect 78 ms 23732 KB Output isn't correct
40 Incorrect 53 ms 24400 KB Output isn't correct
41 Correct 29 ms 10072 KB Output is correct
42 Correct 30 ms 10728 KB Output is correct
43 Correct 25 ms 9688 KB Output is correct
44 Correct 27 ms 10944 KB Output is correct
45 Correct 83 ms 22224 KB Output is correct
46 Incorrect 51 ms 18652 KB Output isn't correct
47 Incorrect 49 ms 24404 KB Output isn't correct
48 Incorrect 44 ms 20052 KB Output isn't correct
49 Correct 29 ms 10580 KB Output is correct
50 Correct 27 ms 9812 KB Output is correct
51 Correct 28 ms 9988 KB Output is correct
52 Correct 27 ms 10876 KB Output is correct
53 Correct 88 ms 22168 KB Output is correct
54 Incorrect 44 ms 17332 KB Output isn't correct