oj.uz

Submission #253838

# Submission time Handle Problem Language Result Execution time Memory
253838 2020-07-28T21:35:59 Z aZvezda Pipes (BOI13_pipes) C++14
35 / 100
 223 ms 21880 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 1e5 + 10;
set<pair<int, int> > g[MAX_N];
int ans[MAX_N], arr[MAX_N];

struct cmp {
    bool operator ()(const int &a, const int &b) const {
        if(g[a].size() == g[b].size()) {
            return a < b;
        }
        return g[a].size() < g[b].size();
    }
};

multiset<int, cmp> pq;

void removeBranches() {
    while(!pq.empty() && g[*(pq.begin())].size() == 1) {
        int curr = *(pq.begin()); pq.erase(pq.begin());
        auto other = *(g[curr].begin());
        ans[other.second] = arr[curr];
        arr[other.first] -= arr[curr];
        g[other.first].erase({curr, other.second});
    }
}

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    if(m > n) {cout << 0 << endl; return 0;}
    for(int i = 1; i <= n; i ++) {
        cin >> arr[i];
    }
    for(int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        g[a].insert({b, i});
        g[b].insert({a, i});
    }
    for(int i = 1; i <= n; i ++) {
        pq.insert(i);
    }
    removeBranches();
    for(int i = 0; i < m; i ++) {
        cout << ans[i] * 2 << endl;
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Incorrect 3 ms 4992 KB Output isn't correct
3 Incorrect 5 ms 5120 KB Output isn't correct
4 Incorrect 208 ms 21752 KB Output isn't correct
5 Incorrect 3 ms 4992 KB Output isn't correct
6 Incorrect 3 ms 4992 KB Output isn't correct
7 Incorrect 3 ms 4992 KB Output isn't correct
8 Incorrect 3 ms 4992 KB Output isn't correct
9 Incorrect 5 ms 5120 KB Output isn't correct
10 Incorrect 4 ms 5120 KB Output isn't correct
11 Incorrect 5 ms 5120 KB Output isn't correct
12 Incorrect 5 ms 5120 KB Output isn't correct
13 Incorrect 161 ms 18292 KB Output isn't correct
14 Incorrect 191 ms 20856 KB Output isn't correct
15 Incorrect 203 ms 21752 KB Output isn't correct
16 Incorrect 171 ms 19192 KB Output isn't correct
17 Incorrect 212 ms 21752 KB Output isn't correct
18 Incorrect 219 ms 21880 KB Output isn't correct
19 Incorrect 187 ms 21752 KB Output isn't correct
20 Incorrect 4 ms 4992 KB Output isn't correct
21 Incorrect 4 ms 5120 KB Output isn't correct
22 Incorrect 208 ms 21752 KB Output isn't correct
23 Incorrect 174 ms 18296 KB Output isn't correct
24 Incorrect 213 ms 21796 KB Output isn't correct
25 Incorrect 167 ms 18936 KB Output isn't correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Incorrect 4 ms 5120 KB Output isn't correct
3 Incorrect 207 ms 20728 KB Output isn't correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Incorrect 3 ms 4992 KB Output isn't correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Incorrect 4 ms 4992 KB Output isn't correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Incorrect 3 ms 4992 KB Output isn't correct
15 Incorrect 5 ms 5120 KB Output isn't correct
16 Incorrect 4 ms 5120 KB Output isn't correct
17 Incorrect 4 ms 5120 KB Output isn't correct
18 Correct 3 ms 5012 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 5120 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Incorrect 5 ms 5120 KB Output isn't correct
23 Incorrect 154 ms 18552 KB Output isn't correct
24 Incorrect 209 ms 21756 KB Output isn't correct
25 Incorrect 196 ms 20856 KB Output isn't correct
26 Correct 4 ms 4992 KB Output is correct
27 Correct 3 ms 4992 KB Output is correct
28 Correct 3 ms 4992 KB Output is correct
29 Correct 3 ms 4992 KB Output is correct
30 Incorrect 186 ms 21368 KB Output isn't correct
31 Incorrect 196 ms 21752 KB Output isn't correct
32 Incorrect 204 ms 21836 KB Output isn't correct
33 Incorrect 211 ms 21752 KB Output isn't correct
34 Correct 3 ms 4992 KB Output is correct
35 Correct 3 ms 4992 KB Output is correct
36 Correct 3 ms 4992 KB Output is correct
37 Correct 4 ms 4992 KB Output is correct
38 Incorrect 191 ms 21752 KB Output isn't correct
39 Incorrect 223 ms 21628 KB Output isn't correct
40 Incorrect 197 ms 21748 KB Output isn't correct
41 Incorrect 184 ms 21752 KB Output isn't correct
42 Correct 4 ms 4992 KB Output is correct
43 Correct 3 ms 4992 KB Output is correct
44 Correct 3 ms 4992 KB Output is correct
45 Correct 3 ms 4992 KB Output is correct
46 Incorrect 192 ms 21772 KB Output isn't correct
47 Incorrect 206 ms 21764 KB Output isn't correct
48 Incorrect 198 ms 21624 KB Output isn't correct
49 Incorrect 205 ms 20856 KB Output isn't correct
50 Correct 3 ms 4992 KB Output is correct
51 Correct 3 ms 4992 KB Output is correct
52 Correct 3 ms 4992 KB Output is correct
53 Correct 4 ms 4992 KB Output is correct
54 Incorrect 209 ms 21500 KB Output isn't correct