Submission #462276

#	Time	Username	Problem	Language	Result	Execution time	Memory
462276		Yeboi	Pipes (BOI13_pipes)	C++14	44.07 / 100	349 ms	32140 KiB

pipes

#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000000000000;
const ll N = 100001;
const ll MOD = 1000000007;
const ll modi = 1000000007;
const ll MAXN = 10000000000;    
const ll rootval = 319;
using namespace std;

ll upedge[N];
vector<ll> adj[N];
ll arr[N];
ll par[N];

void dfs(ll v, ll p){
    ll sum = 0;
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            if(upedge[u] == -1){
                dfs(u,v);
                sum += upedge[u];
            }
        }
    }
    upedge[v] = arr[v] - sum;
}
void parent(ll v, ll p){
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            par[u] = v;
            parent(u,v);
        }
    }
}
int main(){
    fastio();
    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll>> edges;
    rep(i,n){
        cin >> arr[i];
        upedge[i] = -1;
    }
    rep(i,m){
        ll u,v;
        cin >> u >> v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back(make_pair(u,v));
    }
    if(m == n-1){
        rep(i,n){
            if(adj[i].size() == 1){
                upedge[i] = arr[i];
            }
        }
        dfs(0,-1);
        parent(0,-1);
        par[0] = -1;
        map<pair<ll,ll>,ll> mp;
        rep(i,n){
            if(par[i] == -1){
                continue;
            }
            else{
                mp[{i,par[i]}] = upedge[i];
                mp[{par[i],i}] = upedge[i];
            }
        }
        rep(i,edges.size()){
            ll u = edges[i].first;
            ll v = edges[i].second;
            cout << 2*mp[{u,v}] << endl;
        }
    }
    else{
        cout << 0 << endl;
    }
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
   82 |         rep(i,edges.size()){
      |             ~~~~~~~~~~~~~~     
pipes.cpp:82:9: note: in expansion of macro 'rep'
   82 |         rep(i,edges.size()){
      |         ^~~

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