Submission #1247600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247600		Dedibeat	Pipes (BOI13_pipes)	C++20	100 / 100	302 ms	37880 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}

vector<pair<int, int>> adj[100005];
int deg[100005], val[100005], ans[500005];
int vis[100005];
int n, m;
void dfs(int v, vector<pair<int, int>> &cyc, int &edge, int &vert)
{
    vert++;
    vis[v] = 2;
    for(auto &[u, id] : adj[v])
    {
        if(vis[u] == 1) continue;
        edge++;
        if(vis[u] == 2) continue;
        cyc.emplace_back(u, id);
        dfs(u, cyc, edge, vert);
    }
}
int32_t main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> val[i];
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        deg[u]++, deg[v]++;
    }
    queue<int> q;
    auto gogo = [&]()
    {
        for(int i = 1; i <= n; i++)
            if(deg[i] == 1) 
                q.push(i);
        
        while(!q.empty())
        {
            int v = q.front(); q.pop();
            vis[v] = 1;
            for(auto [u, id] : adj[v])
            {
                if(!vis[u])
                {
                    ans[id] = 2 * val[v];
                    val[u] -= val[v];
                    val[v] = 0;
                    if(--deg[u] == 1)
                        q.push(u);
                }
            }
        }
    };

    gogo();
    // print(ans, ans + m);
    // print(val + 1, val + n + 1);

    for(int v = 1; v <= n; v++)
    {
        if(vis[v]) continue;
        vector<pair<int, int>> cyc;
        int edge = 0, vert = 0;
        dfs(v, cyc, edge, vert);
        //cout << edge << " " << vert << endl;
        if(edge / 2 > vert)
        {
            cout << "0\n";
            return 0;
        }
        int tail = cyc.back().F;
        for(auto [u, id] : adj[tail])
        {
            if(u == v) cyc.emplace_back(u, id);
        }

        if(cyc.size() % 2 == 0)
        {
            cout << "0\n";
            return 0;
        }
        reverse(all(cyc));
        int total = 0;
        
        for(auto [u, id] : cyc)
        {
            total += val[u];
        }

        auto [v1, idx] = cyc[0];
        int v2 = cyc[1].F;

        int sum = 0;
        for(int i = 2; i < cyc.size(); i += 2)
        {
            sum += val[cyc[i].F];
        }
        
        int rem = total / 2 - sum;
        ans[idx] = rem * 2;
        val[v1] -= rem; deg[v1]--;
        val[v2] -= rem; deg[v2]--;

        for(int i = 1; i < cyc.size(); i++)
        {
            auto [u, id] = cyc[i];
            ans[id] = 2 * val[u];
            if(i + 1 < cyc.size())
                val[cyc[i + 1].F] -= val[u];
        }
    }

    print(ans, ans + m);







}

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