Submission #251597

#	Time	Username	Problem	Language	Result	Execution time	Memory
251597		abacaba	Pipes (BOI13_pipes)	C++14	48.15 / 100	266 ms	68856 KiB

pipes

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

#define int long long

const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 5e5 + 15;
int n, m, a[N];
vector <int> g[N];
bool used[N];

set <pii> cur;
int deg[N], d[N];

int p[N], sz[N];
pii e[N];
int ans[N];

vector <int> comp[N];

set <int> cycles;
vector <int> inc;

int pp[N];

int pref[2][N];

vector <int> G[N];

bool tw[N];
bool used2[N];

int find(int v) {
    if(v == p[v])
        return v;
    return p[v] = find(p[v]);
}

void unio(int a, int b) {
    a = find(a);
    b = find(b);
    if(a != b) {
        if(sz[a] < sz[b])
            swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
}

inline int gt(int i, int v) {
    return e[i].f == v ? e[i].se : e[i].f;
}

void precheck(int v, int p = -1) {
    used[v] = true;
    pp[v] = p;
    for(int ind : g[v]) {
        int to = gt(ind, v);
        if(to == p)
            continue;
        if(used[to]) {
            if(d[to] > d[v])
                continue;
            if((d[v] - d[to]) & 1) {
                cout << 0 << endl;
                exit(0);
            }
            int u = v;
            while(u != to) {
                unio(u, pp[u]);
                u = pp[u];
            }
        }
        else {
            d[to] = d[v] + 1;
            precheck(to, v);
        }
    }
}

vector <int> now;

void dfs(int v) {
    used[v] = true;
    now.pb(v);
    for(int ind : g[v]) {
        int to = gt(ind, v);
        if(used[to] || find(v) != find(to))
            continue;
        dfs(to);
    }
}

inline int get(int k, int l, int r) {
    k = (k + 10) & 1;
    Max(l, 0LL);
    if(l > r)
        return 0;
    return pref[k][r] - (l == 0 ? 0 : pref[k][l-1]);
}

int calc(int i, int sum) {
    int v = now[i];
    int ind = -1;
    int val;
    if(i + 1 < now.size()) {
        for(int j = 0; j < g[v].size(); ++j)
            if(gt(g[v][j], v) == now[i + 1])
                ind = g[v][j];
        assert(ind != -1);
        val = get(i + 2, i + 2, now.size() - 1) + get(i - 1, 0, i - 1);
    }
    else {
        for(int j = 0; j < g[v].size(); ++j)
            if(gt(g[v][j], v) == now[0])
                ind = g[v][j];
        assert(ind != -1);
        val = get(1, 1, now.size() - 2);
    }
    return ans[ind] = sum - 2 * val;
}

void solve_for_cycle(int s) {
    if(sz[s] == 1)
        return;
    int sum = 0;
    for(int v : now)
        sum += a[v];
    now.clear();
    dfs(comp[s][0]);
    int start = now.size() - 1;
    int x, y;
    for(int ind : G[s]) {
        x = e[ind].f, y = e[ind].se;
        if(find(y) == s)
            swap(x, y);
        int to = find(y);
        if(!used2[to])
            break;
    }
    for(int i = 0; i + 1 < now.size(); ++i) {
        if(now[i] == x) {
            start = i;
            break;
        }
    }
    for(int i = 0; i < now.size(); ++i) {
        for(int j = 0; j < 2; ++j)
            pref[j][i] = (i == 0 ? 0 : pref[j][i-1]);
        pref[i & 1][i] += a[now[i]];
    }
    int prev = calc(start, sum);
    for(int i = start + 1; i < now.size(); ++i) {
        int v = now[i];
        int ind = -1;
        for(int j = 0; j < g[v].size(); ++j)
            if(gt(g[v][j], v) == now[(i + 1) % now.size()])
                ind = g[v][j];
        ans[ind] = 2 * a[v] - prev;
        prev = ans[ind];
    }
    for(int i = 0; i < start; ++i) {
        int v = now[i];
        int ind = -1;
        for(int j = 0; j < g[v].size(); ++j)
            if(gt(g[v][j], v) == now[(i + 1) % now.size()])
                ind = g[v][j];
        ans[ind] = 2 * a[v] - prev;
        prev = ans[ind];
    }
}

main() {
    for(int i = 0; i < N; ++i)
        p[i] = i, sz[i] = 1;
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    // setin("input.txt");
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= m; ++i) {
        cin >> e[i].f >> e[i].se;
        g[e[i].f].pb(i);
        g[e[i].se].pb(i);
    }
    precheck(1);
    for(int v = 1; v <= n; ++v) {
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(find(v) != find(to))
                G[find(v)].pb(ind);
        }
    }
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; ++i) {
        comp[find(i)].pb(i);
        deg[find(i)] = G[find(i)].size();
        cur.insert({deg[find(i)], find(i)});
    }
    while(!cur.empty()) {
        int v = cur.begin()->se;
        cur.erase(cur.begin());

        // cout << "fdfd: " << v << endl;

        used2[v] = true;
        for(int ind : G[v]) {
            int x = e[ind].f, y = e[ind].se;
            if(find(y) == v)
                swap(x, y);
            int to = find(y);
            if(used2[to])
                a[x] -= ans[ind] / 2;
        }
        solve_for_cycle(v);
        for(int ind : G[v]) {
            int x = e[ind].f, y = e[ind].se;
            if(find(y) == v)
                swap(x, y);
            int to = find(y);
            if(used2[to])
                continue;
            ans[ind] = 2 * a[x];
            cur.erase({deg[to], to});
            --deg[to];
            cur.insert({deg[to], to});
        }
    }
    for(int i = 1; i <= n; ++i) {
        int val = 0;
        for(int ind : g[i])
            val += ans[ind] / 2;
        // cout << "asdsa: " << val << endl;
    }
    for(int i = 1; i <= m; ++i)
        cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'long long int calc(long long int, long long int)':
pipes.cpp:164:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i + 1 < now.size()) {
        ~~~~~~^~~~~~~~~~~~
pipes.cpp:165:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:172:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp: In function 'void solve_for_cycle(long long int)':
pipes.cpp:199:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:205:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:211:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = start + 1; i < now.size(); ++i) {
                            ~~^~~~~~~~~~~~
pipes.cpp:214:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:223:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp: At global scope:
pipes.cpp:231:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
pipes.cpp: In function 'void solve_for_cycle(long long int)':
pipes.cpp:200:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(now[i] == x) {
         ^~

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