oj.uz

Submission #251583

# Submission time Handle Problem Language Result Execution time Memory
251583 2020-07-21T19:59:59 Z abacaba Pipes (BOI13_pipes) C++14
18.1481 / 100
 383 ms 130236 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);
                G[find(to)].pb(ind);
            }
        }
    }
    // for(int i = 1; i <= n; ++i)
    //     cout << find(i) << ' ';
    // cout << endl;
    // return 0;
    memset(used, 0, sizeof(used));
    cur.clear();
    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;
            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: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 44032 KB Output isn't correct
2 Incorrect 27 ms 44032 KB Output isn't correct
3 Incorrect 25 ms 44156 KB Output isn't correct
4 Incorrect 312 ms 68216 KB Output isn't correct
5 Incorrect 24 ms 44024 KB Output isn't correct
6 Incorrect 23 ms 43904 KB Output isn't correct
7 Incorrect 23 ms 44024 KB Output isn't correct
8 Incorrect 24 ms 43900 KB Output isn't correct
9 Incorrect 24 ms 44160 KB Output isn't correct
10 Incorrect 25 ms 44152 KB Output isn't correct
11 Incorrect 25 ms 44160 KB Output isn't correct
12 Incorrect 25 ms 44280 KB Output isn't correct
13 Incorrect 277 ms 63416 KB Output isn't correct
14 Incorrect 353 ms 66972 KB Output isn't correct
15 Incorrect 383 ms 68344 KB Output isn't correct
16 Incorrect 268 ms 64760 KB Output isn't correct
17 Incorrect 314 ms 68216 KB Output isn't correct
18 Incorrect 322 ms 68344 KB Output isn't correct
19 Incorrect 298 ms 72056 KB Output isn't correct
20 Incorrect 24 ms 43904 KB Output isn't correct
21 Incorrect 24 ms 44160 KB Output isn't correct
22 Incorrect 315 ms 68344 KB Output isn't correct
23 Incorrect 247 ms 63264 KB Output isn't correct
24 Incorrect 313 ms 68344 KB Output isn't correct
25 Incorrect 264 ms 64252 KB Output isn't correct

Subtask #2
18.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 44032 KB Output isn't correct
2 Incorrect 23 ms 44160 KB Output isn't correct
3 Correct 81 ms 53368 KB Output is correct
4 Runtime error 248 ms 128168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 292 ms 66552 KB Output isn't correct
6 Correct 235 ms 66616 KB Output is correct
7 Incorrect 24 ms 44032 KB Output isn't correct
8 Incorrect 23 ms 44032 KB Output isn't correct
9 Correct 24 ms 43520 KB Output is correct
10 Incorrect 24 ms 44032 KB Output isn't correct
11 Runtime error 70 ms 88824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 24 ms 43904 KB Output isn't correct
13 Correct 23 ms 43520 KB Output is correct
14 Incorrect 32 ms 44024 KB Output isn't correct
15 Incorrect 24 ms 44160 KB Output isn't correct
16 Incorrect 25 ms 44160 KB Output isn't correct
17 Correct 33 ms 43520 KB Output is correct
18 Incorrect 24 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 25 ms 44152 KB Output isn't correct
21 Correct 31 ms 43648 KB Output is correct
22 Incorrect 25 ms 44160 KB Output isn't correct
23 Incorrect 162 ms 61232 KB Output isn't correct
24 Incorrect 223 ms 66032 KB Output isn't correct
25 Correct 94 ms 53368 KB Output is correct
26 Incorrect 218 ms 65392 KB Output isn't correct
27 Runtime error 213 ms 124284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 318 ms 64304 KB Output isn't correct
29 Correct 211 ms 62064 KB Output is correct
30 Incorrect 240 ms 69424 KB Output isn't correct
31 Incorrect 187 ms 63756 KB Output isn't correct
32 Incorrect 286 ms 67540 KB Output isn't correct
33 Correct 81 ms 54264 KB Output is correct
34 Incorrect 293 ms 69732 KB Output isn't correct
35 Runtime error 237 ms 128044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Incorrect 288 ms 65272 KB Output isn't correct
37 Correct 235 ms 66692 KB Output is correct
38 Incorrect 236 ms 68592 KB Output isn't correct
39 Incorrect 297 ms 67708 KB Output isn't correct
40 Incorrect 236 ms 66160 KB Output isn't correct
41 Correct 89 ms 56056 KB Output is correct
42 Incorrect 187 ms 62316 KB Output isn't correct
43 Runtime error 213 ms 124312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Incorrect 291 ms 66516 KB Output isn't correct
45 Correct 179 ms 63224 KB Output is correct
46 Incorrect 238 ms 70000 KB Output isn't correct
47 Incorrect 230 ms 66160 KB Output isn't correct
48 Incorrect 179 ms 63884 KB Output isn't correct
49 Correct 75 ms 51576 KB Output is correct
50 Incorrect 251 ms 66528 KB Output isn't correct
51 Runtime error 339 ms 130236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Incorrect 218 ms 59476 KB Output isn't correct
53 Correct 230 ms 63304 KB Output is correct
54 Incorrect 312 ms 68200 KB Output isn't correct