oj.uz

답안 #1053774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053774 2024-08-11T17:25:48 Z codexistent Pipes (BOI13_pipes) C++14
0 / 100
 102 ms 62416 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
#define MAXM 500005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, m, w[MAXN], d[MAXM];
set<ll> adj[MAXN];
pair<ll, pair<ll, ll>> e[MAXN];
bool v[MAXM];
map<pair<ll, ll>, ll> eid;

int main(){
    cin >> n >> m;
    FOR(i, 1, n) cin >> w[i];
    FOR(i, 1, m){
        e[i].f = 0;
        cin >> e[i].s.f >> e[i].s.s;
        adj[e[i].s.f].insert(e[i].s.s), adj[e[i].s.s].insert(e[i].s.f);

        eid.insert({{min(e[i].s.f, e[i].s.s), max(e[i].s.f, e[i].s.s)}, i});
    }

    /*priority_queue<pair<ll, ll>> pq;
    FOR(i, 1, m) {
        v[i] = false;
        e[i].f = adj[e[i].s.f].size() + adj[e[i].s.s].size() - 2;
        //cout << "FOR EDGE " << i << " WE HAVE " << e[i].f << " CT " << endl;
        for(auto j : adj[e[i].s.f]){
            if(adj[j].size() == 2 && adj[e[i].s.s].find(j) != adj[e[i].s.s].end()){
                e[i].f -= 2;
            }
        }

        if(adj[e[i].s.f].size() == 1 || adj[e[i].s.s].size() == 1){
            pq.push({1, i});
        }else if(e[i].f == 0){
            pq.push({0, i});
        }
    }*/
    /*while(pq.size()){
        //cout << pq.top().f << " ~ " << pq.top().s << " ==> " << e[pq.top().s].f << endl;
        auto pqi = pq.top(); pq.pop();
        if(v[pqi.s]) continue;
        v[pqi.s] = true;

        if(pqi.f == 0){
            ll s = 0;
            for(ll i2 : adj[e[pqi.s].s.f]) s += w[i2];
            for(ll i2 : adj[e[pqi.s].s.s]) s += w[i2];

            d[pqi.s] = w[e[pqi.s].s.f] + w[e[pqi.s].s.s] - s;
        }else if(adj[e[pqi.s].s.f].size() == 1){
            d[pqi.s] = w[e[pqi.s].s.f] * 2;
        }else{
            d[pqi.s] = w[e[pqi.s].s.s] * 2;
        }

        adj[e[pqi.s].s.f].erase(e[pqi.s].s.s);
        adj[e[pqi.s].s.s].erase(e[pqi.s].s.f);
        w[e[pqi.s].s.f] -= d[pqi.s] / 2;
        w[e[pqi.s].s.s] -= d[pqi.s] / 2;

        if(adj[e[pqi.s].s.f].size() == 2){
            ll a = *(adj[e[pqi.s].s.f].begin());
            ll b = *(++adj[e[pqi.s].s.f].begin());

            if(eid.find({min(a, b), max(a, b)}) != eid.end()){
                e[eid[{min(a, b), max(a, b)}]].f -= 2;

                if(!v[eid[{min(a, b), max(a, b)}]] && e[eid[{min(a, b), max(a, b)}]].f == 0){
                    pq.push({0, eid[{min(a, b), max(a, b)}]});
                }
            }
        }else if(adj[e[pqi.s].s.f].size() == 1){
            ll a = *(adj[e[pqi.s].s.f].begin());
            if(!v[eid[{min(a, e[pqi.s].s.f), max(a, e[pqi.s].s.f)}]]){
                pq.push({1, eid[{min(a, e[pqi.s].s.f), max(a, e[pqi.s].s.f)}]});
            }
        }

        if(adj[e[pqi.s].s.s].size() == 2){
            ll a = *(adj[e[pqi.s].s.s].begin());
            ll b = *(++adj[e[pqi.s].s.s].begin());

            if(eid.find({min(a, b), max(a, b)}) != eid.end()){
                e[eid[{min(a, b), max(a, b)}]].f -= 2;

                if(!v[eid[{min(a, b), max(a, b)}]] && e[eid[{min(a, b), max(a, b)}]].f == 0){
                    pq.push({0, eid[{min(a, b), max(a, b)}]});
                }
            }
        }else if(adj[e[pqi.s].s.s].size() == 1){
            ll a = *(adj[e[pqi.s].s.s].begin());
            if(!v[eid[{min(a, e[pqi.s].s.s), max(a, e[pqi.s].s.s)}]]){
                pq.push({1, eid[{min(a, e[pqi.s].s.s), max(a, e[pqi.s].s.s)}]});
            }
        }
    }

    FOR(i, 1, m) if(!v[i]){
        cout << 0 << endl;
        return 0;
    } 

    FOR(i, 1, m) cout << d[i] << endl;*/
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Incorrect 2 ms 8796 KB Output isn't correct
4 Incorrect 74 ms 24920 KB Output isn't correct
5 Incorrect 1 ms 8540 KB Output isn't correct
6 Incorrect 1 ms 8540 KB Output isn't correct
7 Incorrect 1 ms 8540 KB Output isn't correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Incorrect 1 ms 8796 KB Output isn't correct
10 Incorrect 1 ms 8796 KB Output isn't correct
11 Incorrect 1 ms 8624 KB Output isn't correct
12 Incorrect 1 ms 8796 KB Output isn't correct
13 Incorrect 58 ms 21544 KB Output isn't correct
14 Incorrect 63 ms 23852 KB Output isn't correct
15 Incorrect 63 ms 24976 KB Output isn't correct
16 Incorrect 56 ms 22480 KB Output isn't correct
17 Incorrect 65 ms 24916 KB Output isn't correct
18 Incorrect 63 ms 24912 KB Output isn't correct
19 Incorrect 64 ms 24852 KB Output isn't correct
20 Incorrect 1 ms 8536 KB Output isn't correct
21 Incorrect 1 ms 8792 KB Output isn't correct
22 Incorrect 73 ms 25008 KB Output isn't correct
23 Incorrect 50 ms 21496 KB Output isn't correct
24 Incorrect 64 ms 24904 KB Output isn't correct
25 Incorrect 54 ms 22084 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Incorrect 1 ms 8796 KB Output isn't correct
3 Incorrect 73 ms 24064 KB Output isn't correct
4 Incorrect 62 ms 24912 KB Output isn't correct
5 Incorrect 61 ms 24400 KB Output isn't correct
6 Runtime error 90 ms 59216 KB Execution killed with signal 11
7 Incorrect 1 ms 8536 KB Output isn't correct
8 Incorrect 1 ms 8540 KB Output isn't correct
9 Incorrect 1 ms 8540 KB Output isn't correct
10 Incorrect 1 ms 8540 KB Output isn't correct
11 Incorrect 1 ms 8540 KB Output isn't correct
12 Incorrect 1 ms 8656 KB Output isn't correct
13 Incorrect 1 ms 8540 KB Output isn't correct
14 Incorrect 1 ms 8540 KB Output isn't correct
15 Incorrect 1 ms 8796 KB Output isn't correct
16 Incorrect 2 ms 8796 KB Output isn't correct
17 Incorrect 1 ms 8796 KB Output isn't correct
18 Incorrect 1 ms 8792 KB Output isn't correct
19 Incorrect 1 ms 8796 KB Output isn't correct
20 Incorrect 2 ms 8796 KB Output isn't correct
21 Incorrect 4 ms 8900 KB Output isn't correct
22 Incorrect 1 ms 8796 KB Output isn't correct
23 Incorrect 54 ms 21732 KB Output isn't correct
24 Incorrect 65 ms 24912 KB Output isn't correct
25 Incorrect 63 ms 23892 KB Output isn't correct
26 Incorrect 76 ms 24916 KB Output isn't correct
27 Incorrect 64 ms 24916 KB Output isn't correct
28 Incorrect 66 ms 25688 KB Output isn't correct
29 Runtime error 102 ms 62416 KB Execution killed with signal 11
30 Incorrect 65 ms 24656 KB Output isn't correct
31 Incorrect 74 ms 24916 KB Output isn't correct
32 Incorrect 65 ms 24912 KB Output isn't correct
33 Incorrect 66 ms 24908 KB Output isn't correct
34 Incorrect 70 ms 24896 KB Output isn't correct
35 Incorrect 80 ms 24916 KB Output isn't correct
36 Incorrect 72 ms 25172 KB Output isn't correct
37 Runtime error 92 ms 59188 KB Execution killed with signal 11
38 Incorrect 64 ms 24912 KB Output isn't correct
39 Incorrect 64 ms 24916 KB Output isn't correct
40 Incorrect 71 ms 24808 KB Output isn't correct
41 Incorrect 64 ms 24916 KB Output isn't correct
42 Incorrect 70 ms 24832 KB Output isn't correct
43 Incorrect 66 ms 24912 KB Output isn't correct
44 Incorrect 62 ms 24396 KB Output isn't correct
45 Runtime error 91 ms 54224 KB Execution killed with signal 11
46 Incorrect 69 ms 24912 KB Output isn't correct
47 Incorrect 63 ms 24912 KB Output isn't correct
48 Incorrect 63 ms 24916 KB Output isn't correct
49 Incorrect 64 ms 23964 KB Output isn't correct
50 Incorrect 73 ms 24916 KB Output isn't correct
51 Incorrect 93 ms 24912 KB Output isn't correct
52 Incorrect 75 ms 24660 KB Output isn't correct
53 Runtime error 85 ms 55888 KB Execution killed with signal 11
54 Incorrect 66 ms 24624 KB Output isn't correct