oj.uz

답안 #251597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251597 2020-07-22T02:28:37 Z abacaba Pipes (BOI13_pipes) C++14
48.1481 / 100
 266 ms 68856 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]);
}

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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 43904 KB Output is correct
2 Correct 23 ms 44024 KB Output is correct
3 Correct 24 ms 44152 KB Output is correct
4 Correct 246 ms 66936 KB Output is correct
5 Correct 24 ms 43896 KB Output is correct
6 Correct 24 ms 44032 KB Output is correct
7 Correct 29 ms 43896 KB Output is correct
8 Correct 28 ms 44032 KB Output is correct
9 Correct 31 ms 44152 KB Output is correct
10 Correct 25 ms 44160 KB Output is correct
11 Correct 30 ms 44128 KB Output is correct
12 Correct 25 ms 44160 KB Output is correct
13 Correct 212 ms 62200 KB Output is correct
14 Correct 236 ms 65524 KB Output is correct
15 Correct 246 ms 66808 KB Output is correct
16 Correct 200 ms 63480 KB Output is correct
17 Correct 266 ms 66808 KB Output is correct
18 Correct 242 ms 66808 KB Output is correct
19 Correct 234 ms 68856 KB Output is correct
20 Correct 23 ms 43904 KB Output is correct
21 Correct 24 ms 44160 KB Output is correct
22 Correct 241 ms 66808 KB Output is correct
23 Correct 183 ms 62072 KB Output is correct
24 Correct 246 ms 66808 KB Output is correct
25 Correct 198 ms 62972 KB Output is correct

Subtask #2
18.1481481481 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 44032 KB Output isn't correct
2 Incorrect 25 ms 44208 KB Output isn't correct
3 Correct 81 ms 53368 KB Output is correct
4 Incorrect 182 ms 63724 KB Output isn't correct
5 Incorrect 231 ms 65016 KB Output isn't correct
6 Correct 239 ms 66680 KB Output is correct
7 Incorrect 23 ms 44032 KB Output isn't correct
8 Incorrect 23 ms 44032 KB Output isn't correct
9 Correct 23 ms 43520 KB Output is correct
10 Incorrect 24 ms 43904 KB Output isn't correct
11 Incorrect 24 ms 43904 KB Output isn't correct
12 Incorrect 24 ms 44032 KB Output isn't correct
13 Correct 27 ms 43520 KB Output is correct
14 Incorrect 23 ms 44032 KB Output isn't correct
15 Incorrect 24 ms 44288 KB Output isn't correct
16 Incorrect 24 ms 44160 KB Output isn't correct
17 Correct 24 ms 43520 KB Output is correct
18 Incorrect 32 ms 44160 KB Output isn't correct
19 Incorrect 24 ms 44160 KB Output isn't correct
20 Incorrect 29 ms 44152 KB Output isn't correct
21 Correct 24 ms 43648 KB Output is correct
22 Incorrect 24 ms 44160 KB Output isn't correct
23 Incorrect 164 ms 60656 KB Output isn't correct
24 Incorrect 215 ms 64876 KB Output isn't correct
25 Correct 83 ms 53368 KB Output is correct
26 Incorrect 196 ms 64204 KB Output isn't correct
27 Incorrect 171 ms 62184 KB Output isn't correct
28 Incorrect 252 ms 63224 KB Output isn't correct
29 Correct 191 ms 62072 KB Output is correct
30 Incorrect 198 ms 66796 KB Output isn't correct
31 Incorrect 174 ms 63340 KB Output isn't correct
32 Incorrect 246 ms 66436 KB Output isn't correct
33 Correct 84 ms 54264 KB Output is correct
34 Incorrect 228 ms 67448 KB Output isn't correct
35 Incorrect 177 ms 63884 KB Output isn't correct
36 Incorrect 237 ms 63992 KB Output isn't correct
37 Correct 235 ms 66552 KB Output is correct
38 Incorrect 232 ms 66380 KB Output isn't correct
39 Incorrect 246 ms 66424 KB Output isn't correct
40 Incorrect 199 ms 65000 KB Output isn't correct
41 Correct 93 ms 56312 KB Output is correct
42 Incorrect 175 ms 61676 KB Output isn't correct
43 Incorrect 161 ms 62188 KB Output isn't correct
44 Incorrect 245 ms 65028 KB Output isn't correct
45 Correct 214 ms 63228 KB Output is correct
46 Incorrect 230 ms 68080 KB Output isn't correct
47 Incorrect 231 ms 65008 KB Output isn't correct
48 Incorrect 188 ms 63596 KB Output isn't correct
49 Correct 78 ms 51576 KB Output is correct
50 Incorrect 202 ms 64880 KB Output isn't correct
51 Incorrect 202 ms 63952 KB Output isn't correct
52 Incorrect 169 ms 58616 KB Output isn't correct
53 Correct 193 ms 63352 KB Output is correct
54 Incorrect 214 ms 66844 KB Output isn't correct