Submission #860744

#	Time	Username	Problem	Language	Result	Execution time	Memory
860744		Ellinor	Pipes (BOI13_pipes)	C++14	30 / 100	643 ms	131072 KiB

pipes

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

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int N, M; //
vector<int> net;

//
vector<vector<pii>> graph; // tree 30p

vector<int> ans;


ll dfs(int node, int par, int kant) // kant ?
{
    ll c = 0;
    rep(i,0,graph[node].size()) {
        if (graph[node][i].first != par) {
            c += dfs(graph[node][i].first, node, graph[node][i].second);
        }
    }
    if (kant != -1)
    {
        return ans[kant] = net[node] - c;
    }
    return 0;
}


int32_t main()
{
    fast();
    cin >> N >> M;
    net.assign(N, 0);
    rep(i,0,N) {
        cin >> net[i];
    }
    graph.assign(N, {});
    int a, b;
    rep(i,0,M) {
        cin >> a >> b;
        a--; b--; //
        graph[a].pb({b, i});
        graph[b].pb({a, i});
    }

    ans.assign(M, -1);
    dfs(1, -1, -1);
    rep(i,0,M) {
        // not tree, can know ?
        cout << ans[i] * 2 << "\n";
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70