답안 #1051119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051119	2024-08-09T20:21:41 Z	ortsac	Pipes (BOI13_pipes)	C++17	74.0741 / 100	96 ms	45488 KB

pipes

#include <bits/stdc++.h>
 
using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

const int MAXN = 1e5 + 10;
const int MAXM = 5e5 + 10;
vector<pii> adj[MAXN];
int bEdge = -1;
vector<pii> edges;
int h[MAXN];
int change[MAXN];
bool vis[MAXN];
int dad[MAXN];
int dp[MAXN];
int peso[MAXM];

void dfs(int node) {
    vis[node] = 1;
    for (auto [u, z] : adj[node]) {
        if (u == dad[node]) continue;
        if (vis[u]) bEdge = z;
        else {
            dad[u] = node;
            h[u] = h[node] + 1;
            dfs(u);
        }
    }
}

void calc(int node) {
    vis[node] = 1;
    for (auto [u, z] : adj[node]) {
        if (vis[u]) continue;
        calc(u);
        dp[node] += (change[u] - dp[u]);
        peso[z] += (change[u] - dp[u]);
    }
}

vector<int> path;
bool found = 0;
int need;

void cPath(int from, int to) {
    path.clear();
    while (to != from) {
        path.push_back(to);
        to = dad[to];
    }
    path.push_back(from);
    reverse(path.begin(), path.end());
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> change[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({a, b});
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    if (m > n) {
        cout << "0\n";
        return 0;
    }
    dfs(1);
    int lca = 0;
    if (bEdge != -1) {
        auto u = edges[bEdge];
        int a = u.fr, b = u.se;
        if (h[b] > h[a]) swap(a, b);
        lca = b;
        int tam = h[a] + h[b] - 2*h[lca] + 1;
        if ((tam % 2LL) == 0) {
            cout << "0\n";
            return 0;
        }
    }
    memset(vis, 0, sizeof vis);
    calc(1);
    if (dp[1] == change[1]) {
        for (int i = 0; i < m; i++) cout << 2*peso[i] << "\n";
        return 0;
    }
    // first case is for tree
    // second case is if you can't add 2x to it
    if ((bEdge == -1) || ((change[1] - dp[1]) % 2LL)) {
        cout << "0\n";
        return 0;
    }
    need = (change[1] - dp[1])/2LL;
    cPath(1, lca);
    int tam = path.size();
    int inv = 1;
    for (int i = 0; i < (tam - 1); i++) {
        int node = path[i];
        int prox = path[i + 1];
        for (auto [u, z] : adj[node]) {
            if (u == prox) {
                peso[z] += 2*need*inv;
                inv = -inv;
                break;
            }
        }
    }
    int a = edges[bEdge].fr, b = edges[bEdge].se;
    if (h[b] > h[a]) swap(a, b);
    cPath(lca, a);
    tam = path.size();
    for (int i = 0; i < (tam - 1); i++) {
        int node = path[i];
        int prox = path[i + 1];
        for (auto [u, z] : adj[node]) {
            if (u == prox) {
                peso[z] += need*inv;
                inv = -inv;
                break;
            }
        }
    }
    if ((h[a] - h[lca]) % 2LL) inv = -inv;
    peso[bEdge] += inv*need;
    for (int i = 0; i < m; i++) {
        cout << peso[i] << "\n";
    }
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	5468 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	1 ms	5724 KB	Output is correct
4	Correct	33 ms	18548 KB	Output is correct
5	Correct	1 ms	5464 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5468 KB	Output is correct
8	Correct	1 ms	5672 KB	Output is correct
9	Correct	1 ms	5724 KB	Output is correct
10	Correct	1 ms	5724 KB	Output is correct
11	Correct	1 ms	5724 KB	Output is correct
12	Correct	1 ms	5724 KB	Output is correct
13	Correct	27 ms	14968 KB	Output is correct
14	Correct	29 ms	16328 KB	Output is correct
15	Correct	32 ms	16840 KB	Output is correct
16	Correct	27 ms	15452 KB	Output is correct
17	Correct	31 ms	18364 KB	Output is correct
18	Correct	41 ms	18636 KB	Output is correct
19	Correct	36 ms	22464 KB	Output is correct
20	Correct	1 ms	5468 KB	Output is correct
21	Correct	1 ms	5724 KB	Output is correct
22	Correct	31 ms	18456 KB	Output is correct
23	Correct	25 ms	15048 KB	Output is correct
24	Correct	35 ms	16836 KB	Output is correct
25	Correct	27 ms	17100 KB	Output is correct

Subtask #2

44.0740740741 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	5468 KB	Output isn't correct
2	Incorrect	1 ms	5724 KB	Output isn't correct
3	Correct	25 ms	16136 KB	Output is correct
4	Correct	23 ms	13764 KB	Output is correct
5	Correct	26 ms	13516 KB	Output is correct
6	Correct	96 ms	45400 KB	Output is correct
7	Incorrect	1 ms	5468 KB	Output isn't correct
8	Incorrect	1 ms	5468 KB	Output isn't correct
9	Correct	1 ms	5468 KB	Output is correct
10	Correct	1 ms	5468 KB	Output is correct
11	Correct	1 ms	5468 KB	Output is correct
12	Correct	1 ms	5468 KB	Output is correct
13	Correct	1 ms	5468 KB	Output is correct
14	Incorrect	1 ms	5468 KB	Output isn't correct
15	Incorrect	1 ms	5724 KB	Output isn't correct
16	Incorrect	1 ms	5724 KB	Output isn't correct
17	Correct	1 ms	5976 KB	Output is correct
18	Correct	1 ms	5720 KB	Output is correct
19	Correct	1 ms	5724 KB	Output is correct
20	Correct	1 ms	5724 KB	Output is correct
21	Correct	1 ms	5724 KB	Output is correct
22	Incorrect	1 ms	5724 KB	Output isn't correct
23	Incorrect	39 ms	20156 KB	Output isn't correct
24	Incorrect	36 ms	21964 KB	Output isn't correct
25	Correct	24 ms	16076 KB	Output is correct
26	Correct	25 ms	13980 KB	Output is correct
27	Correct	27 ms	13748 KB	Output is correct
28	Correct	27 ms	14276 KB	Output is correct
29	Correct	82 ms	38580 KB	Output is correct
30	Incorrect	42 ms	26048 KB	Output isn't correct
31	Incorrect	40 ms	27076 KB	Output isn't correct
32	Incorrect	37 ms	18624 KB	Output isn't correct
33	Correct	31 ms	17348 KB	Output is correct
34	Correct	27 ms	14028 KB	Output is correct
35	Correct	26 ms	13772 KB	Output is correct
36	Correct	25 ms	14020 KB	Output is correct
37	Correct	95 ms	45488 KB	Output is correct
38	Incorrect	39 ms	23488 KB	Output isn't correct
39	Incorrect	36 ms	17856 KB	Output isn't correct
40	Incorrect	42 ms	23336 KB	Output isn't correct
41	Correct	28 ms	19392 KB	Output is correct
42	Correct	23 ms	13764 KB	Output is correct
43	Correct	23 ms	13768 KB	Output is correct
44	Correct	22 ms	13736 KB	Output is correct
45	Correct	74 ms	41644 KB	Output is correct
46	Incorrect	45 ms	25024 KB	Output isn't correct
47	Incorrect	40 ms	21780 KB	Output isn't correct
48	Incorrect	44 ms	25036 KB	Output isn't correct
49	Correct	27 ms	14144 KB	Output is correct
50	Correct	23 ms	13832 KB	Output is correct
51	Correct	22 ms	13764 KB	Output is correct
52	Correct	23 ms	13760 KB	Output is correct
53	Correct	76 ms	40948 KB	Output is correct
54	Incorrect	42 ms	22716 KB	Output isn't correct