oj.uz

Submission #251584

# Submission time Handle Problem Language Result Execution time Memory
251584 2020-07-21T20:06:35 Z abacaba Pipes (BOI13_pipes) C++14
48.1481 / 100
 301 ms 128200 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 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]);
}

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 = 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];
        assert(ind != -1);
        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];
    assert(ind != -1);
    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 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());

        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 <= m; ++i)
        cout << ans[i] << endl;
    return 0;
}

Compilation message

pipes.cpp: In function 'void solve_for_cycle(long long int)':
pipes.cpp:168:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < now.size(); ++i) {
                    ~~^~~~~~~~~~~~
pipes.cpp:173:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < now.size(); ++i) {
                    ~~~~~~^~~~~~~~~~~~
pipes.cpp:176:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < g[v].size(); ++j)
                        ~~^~~~~~~~~~~~~
pipes.cpp:185: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:193: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 23 ms 43904 KB Output is correct
2 Correct 23 ms 44032 KB Output is correct
3 Correct 24 ms 44160 KB Output is correct
4 Correct 240 ms 66680 KB Output is correct
5 Correct 27 ms 43896 KB Output is correct
6 Correct 27 ms 44032 KB Output is correct
7 Correct 23 ms 44024 KB Output is correct
8 Correct 23 ms 44032 KB Output is correct
9 Correct 30 ms 44160 KB Output is correct
10 Correct 31 ms 44340 KB Output is correct
11 Correct 28 ms 44152 KB Output is correct
12 Correct 26 ms 44160 KB Output is correct
13 Correct 259 ms 62072 KB Output is correct
14 Correct 295 ms 65528 KB Output is correct
15 Correct 236 ms 66936 KB Output is correct
16 Correct 206 ms 63352 KB Output is correct
17 Correct 278 ms 66772 KB Output is correct
18 Correct 265 ms 66808 KB Output is correct
19 Correct 263 ms 68856 KB Output is correct
20 Correct 23 ms 43904 KB Output is correct
21 Correct 39 ms 44152 KB Output is correct
22 Correct 243 ms 66876 KB Output is correct
23 Correct 254 ms 62268 KB Output is correct
24 Correct 255 ms 66936 KB Output is correct
25 Correct 204 ms 62968 KB Output is correct

Subtask #2
18.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 43916 KB Output isn't correct
2 Incorrect 27 ms 44160 KB Output isn't correct
3 Correct 88 ms 53240 KB Output is correct
4 Runtime error 279 ms 127632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 243 ms 65016 KB Output isn't correct
6 Correct 236 ms 66556 KB Output is correct
7 Incorrect 25 ms 44032 KB Output isn't correct
8 Incorrect 27 ms 44032 KB Output isn't correct
9 Correct 27 ms 43512 KB Output is correct
10 Incorrect 24 ms 44032 KB Output isn't correct
11 Runtime error 74 ms 88912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 24 ms 44032 KB Output isn't correct
13 Correct 24 ms 43520 KB Output is correct
14 Incorrect 23 ms 44032 KB Output isn't correct
15 Incorrect 25 ms 44160 KB Output isn't correct
16 Incorrect 28 ms 44160 KB Output isn't correct
17 Correct 27 ms 43520 KB Output is correct
18 Incorrect 25 ms 44160 KB Output isn't correct
19 Runtime error 70 ms 89208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 24 ms 44160 KB Output isn't correct
21 Correct 24 ms 43648 KB Output is correct
22 Incorrect 26 ms 44160 KB Output isn't correct
23 Incorrect 149 ms 60528 KB Output isn't correct
24 Incorrect 199 ms 64740 KB Output isn't correct
25 Correct 83 ms 53240 KB Output is correct
26 Incorrect 235 ms 64240 KB Output isn't correct
27 Runtime error 233 ms 124216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 280 ms 63224 KB Output isn't correct
29 Correct 239 ms 62072 KB Output is correct
30 Incorrect 196 ms 66664 KB Output isn't correct
31 Incorrect 167 ms 63216 KB Output isn't correct
32 Incorrect 236 ms 66408 KB Output isn't correct
33 Correct 88 ms 54252 KB Output is correct
34 Incorrect 229 ms 67448 KB Output isn't correct
35 Runtime error 242 ms 127748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Incorrect 236 ms 63992 KB Output isn't correct
37 Correct 231 ms 66556 KB Output is correct
38 Incorrect 204 ms 66172 KB Output isn't correct
39 Incorrect 246 ms 66404 KB Output isn't correct
40 Incorrect 198 ms 64876 KB Output isn't correct
41 Correct 94 ms 56184 KB Output is correct
42 Incorrect 173 ms 61396 KB Output isn't correct
43 Runtime error 208 ms 124140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Incorrect 247 ms 65016 KB Output isn't correct
45 Correct 182 ms 63224 KB Output is correct
46 Incorrect 204 ms 67952 KB Output isn't correct
47 Incorrect 211 ms 64876 KB Output isn't correct
48 Incorrect 169 ms 63416 KB Output isn't correct
49 Correct 83 ms 51576 KB Output is correct
50 Incorrect 203 ms 64880 KB Output isn't correct
51 Runtime error 301 ms 128200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Incorrect 174 ms 58488 KB Output isn't correct
53 Correct 195 ms 63300 KB Output is correct
54 Incorrect 200 ms 66544 KB Output isn't correct