Submission #307067

#	Time	Username	Problem	Language	Result	Execution time	Memory
307067		ant101	Pipes (BOI13_pipes)	C++14	100 / 100	64 ms	15480 KiB

pipes

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

ll c[maxn], ans[maxn];
pll p[maxn];
int ID;

int tp[maxn], to[maxn], nxt[maxn];

void add_edge(int a, int b){
    static int C = 0;
    nxt[C] = tp[a], tp[a] = C, to[C] = b, C++;
}

int mark[maxn];

pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}

void dfs(int u, int par = -1){
    p[u].F = c[u];
    mark[u] = 1;
    for(int id = tp[u]; id != -1; id = nxt[id]){
        if(mark[to[id]] == 1 && to[id] != par){
            if(ID == -1)
                ID = id >> 1;
            if(ID != (id >> 1))
                cout << 0 << endl, exit(0);
            p[u].S--;
        }
        else if(mark[to[id]] != 1){
            dfs(to[id], u);
            p[u]= p[u] - p[to[id]];
        }
    }
}
void go(int u){
    mark[u] = 2;
    for(int id = tp[u]; id != -1; id = nxt[id]){
        if(mark[to[id]] != 2){
            go(to[id]);
            ans[id >> 1] = p[to[id]].F + 1ll * (ID == -1 ? 0 : ans[ID]) * p[to[id]].S;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    
    memset(tp, -1, sizeof tp);
    
    int n, m;
    cin >> n >> m;
    
    if(m > n)
        return cout << 0 << endl, 0;
    
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
    }
    for(int i = 1; i <= n; i++){
        if(mark[i] == 0){
            ID = -1;
            dfs(i);
            if(ID == -1){
                if(! (p[i].F == 0 && p[i].S == 0) )
                    return cout << 0 << endl, 0;
            }
            else{
                if(p[i].S == 0)
                    return cout << 0 << endl, 0;
                if(p[i].F % p[i].S != 0)
                    return cout << 0 << endl, 0;
                ans[ID] = -(p[i].F / p[i].S);
            }
            go(i);
        }
    }
    for(int i = 0; i < m; i++){
        cout << 2ll * ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

pipes.cpp:61: warning: "sz" redefined
   61 | #define sz(s) int((s).size())
      | 
pipes.cpp:40: note: this is the location of the previous definition
   40 | #define sz(x) (int)x.size()
      |

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