oj.uz

Submission #251581

# Submission time Handle Problem Language Result Execution time Memory
251581 2020-07-21T19:52:10 Z abacaba Pipes (BOI13_pipes) C++14
48.1481 / 100
 369 ms 66296 KB 
#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 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;
    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);
            }
        }
        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]);
}

void solve_for_cycle(int s) {
    if(sz[s] == 1)
        return;
    now.clear();
    dfs(comp[s][0]);
    int sum = 0;
    for(int v : now)
        sum += a[v];
    for(int i : now)
        cout << i << ' ';
    cout << endl;
    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]];
    }
    for(int i = 0; i + 1 < 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])
                ind = g[v][j];
        if(ind == -1)
            exit(0);
        int val = get(i + 2, i + 2, now.size() - 1) + get(i - 1, 0, i - 1);
        ans[ind] = sum - 2 * val;
    }
    int v = now.back();
    int ind = -1;
    for(int j = 0; j < g[v].size(); ++j)
        if(gt(g[v][j], v) == now[0])
            ind = g[v][j];
    int val = get(1, 1, now.size() - 2);
    ans[ind] = sum - 2 * val;
}

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 i = 1; i <= n; ++i)
        deg[i] = g[i].size(), cur.insert({g[i].size(), i});
    memset(used, 0, sizeof(used));
    while(!cur.empty()) {
        int v = cur.begin()->se;
        cur.erase(cur.begin());
        used[v] = true;
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to] && deg[to] == 0)
                a[v] -= ans[ind] / 2;
        }
        if(deg[v] != 1)
            continue;
        deg[v] = 0;
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(used[to])
                continue;
            ans[ind] = 2 * a[v];
            cur.erase({deg[to], to});
            --deg[to];
            cur.insert({deg[to], to});
        }
    }
    for(int v = 1; v <= n; ++v) {
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(deg[v] > 1 && deg[to] > 1)
                unio(v, to);
        }
    }
    for(int v = 1; v <= n; ++v) {
        for(int ind : g[v]) {
            int to = gt(ind, v);
            if(find(v) != find(to) && deg[v] != 0 && deg[to] != 0) {
                G[find(v)].pb(ind);
                G[find(to)].pb(ind);
            }
        }
    }
    memset(used, 0, sizeof(used));
    cur.clear();
    for(int i = 1; i <= n; ++i) {
        if(deg[find(i)] != 0) {
            comp[find(i)].pb(i);
            deg[find(i)] = G[find(i)].size();
            cur.insert({deg[find(i)], find(i)});
        }
    }

    memset(used, 0, sizeof(used));
    while(!cur.empty()) {
        int v = cur.begin()->se;
        cur.erase(cur.begin());

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

Compilation message

pipes.cpp: In function 'void solve_for_cycle(long long int)':
pipes.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:168:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:171:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:181:22: 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:188:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 43904 KB Output is correct
2 Correct 23 ms 43904 KB Output is correct
3 Correct 24 ms 44024 KB Output is correct
4 Correct 203 ms 59000 KB Output is correct
5 Correct 23 ms 43904 KB Output is correct
6 Correct 27 ms 44032 KB Output is correct
7 Correct 24 ms 43904 KB Output is correct
8 Correct 27 ms 43896 KB Output is correct
9 Correct 24 ms 44032 KB Output is correct
10 Correct 24 ms 44032 KB Output is correct
11 Correct 24 ms 44024 KB Output is correct
12 Correct 24 ms 44152 KB Output is correct
13 Correct 175 ms 56060 KB Output is correct
14 Correct 191 ms 58236 KB Output is correct
15 Correct 226 ms 59060 KB Output is correct
16 Correct 194 ms 56824 KB Output is correct
17 Correct 241 ms 59000 KB Output is correct
18 Correct 237 ms 59128 KB Output is correct
19 Correct 271 ms 61692 KB Output is correct
20 Correct 24 ms 43896 KB Output is correct
21 Correct 24 ms 44032 KB Output is correct
22 Correct 219 ms 59132 KB Output is correct
23 Correct 167 ms 55932 KB Output is correct
24 Correct 212 ms 59128 KB Output is correct
25 Correct 172 ms 56608 KB Output is correct

Subtask #2
18.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 43904 KB Output isn't correct
2 Incorrect 24 ms 44160 KB Output isn't correct
3 Correct 89 ms 52600 KB Output is correct
4 Incorrect 194 ms 62840 KB Output isn't correct
5 Incorrect 197 ms 58232 KB Output isn't correct
6 Correct 254 ms 66240 KB Output is correct
7 Incorrect 24 ms 43896 KB Output isn't correct
8 Incorrect 24 ms 43904 KB Output isn't correct
9 Correct 23 ms 43392 KB Output is correct
10 Incorrect 23 ms 43904 KB Output isn't correct
11 Incorrect 28 ms 43904 KB Output isn't correct
12 Incorrect 27 ms 43904 KB Output isn't correct
13 Correct 27 ms 43392 KB Output is correct
14 Incorrect 27 ms 43904 KB Output isn't correct
15 Incorrect 24 ms 44160 KB Output isn't correct
16 Incorrect 28 ms 44160 KB Output isn't correct
17 Correct 23 ms 43520 KB Output is correct
18 Incorrect 25 ms 44160 KB Output isn't correct
19 Incorrect 24 ms 44160 KB Output isn't correct
20 Incorrect 25 ms 44160 KB Output isn't correct
21 Correct 25 ms 43648 KB Output is correct
22 Incorrect 25 ms 44160 KB Output isn't correct
23 Incorrect 159 ms 58872 KB Output isn't correct
24 Incorrect 207 ms 61560 KB Output isn't correct
25 Correct 96 ms 52544 KB Output is correct
26 Incorrect 196 ms 62372 KB Output isn't correct
27 Incorrect 240 ms 62500 KB Output isn't correct
28 Incorrect 291 ms 58616 KB Output isn't correct
29 Correct 369 ms 61944 KB Output is correct
30 Incorrect 350 ms 63224 KB Output isn't correct
31 Incorrect 196 ms 63480 KB Output isn't correct
32 Incorrect 216 ms 59512 KB Output isn't correct
33 Correct 82 ms 53496 KB Output is correct
34 Incorrect 193 ms 61672 KB Output isn't correct
35 Incorrect 207 ms 62840 KB Output isn't correct
36 Incorrect 192 ms 58488 KB Output isn't correct
37 Correct 237 ms 66296 KB Output is correct
38 Incorrect 202 ms 62712 KB Output isn't correct
39 Incorrect 211 ms 59128 KB Output isn't correct
40 Incorrect 216 ms 61464 KB Output isn't correct
41 Correct 113 ms 55288 KB Output is correct
42 Incorrect 214 ms 61944 KB Output isn't correct
43 Incorrect 242 ms 63224 KB Output isn't correct
44 Incorrect 241 ms 58232 KB Output isn't correct
45 Correct 203 ms 63096 KB Output is correct
46 Incorrect 204 ms 63992 KB Output isn't correct
47 Incorrect 204 ms 61432 KB Output isn't correct
48 Incorrect 192 ms 63352 KB Output isn't correct
49 Correct 94 ms 50936 KB Output is correct
50 Incorrect 192 ms 61816 KB Output isn't correct
51 Incorrect 200 ms 60280 KB Output isn't correct
52 Incorrect 187 ms 59512 KB Output isn't correct
53 Correct 193 ms 63224 KB Output is correct
54 Incorrect 211 ms 62200 KB Output isn't correct