oj.uz

Submission #171843

# Submission time Handle Problem Language Result Execution time Memory
171843 2019-12-30T13:23:55 Z godwind Alkemija (COCI18_alkemija) C++14
56 / 80
 1000 ms 29168 KB 
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>

using namespace std;

// #define int long long
#define double long double
#define less less228
#define left left228
#define right right228

template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}


random_device rnd;

template<typename T> void shuffle(vector< T > &v) {
    for (int i = 1; i < (int)v.size(); ++i) {
        swap(v[rnd() % i], v[i]);
    }
    for (int i = (int)v.size() - 1; i; --i) {
        swap(v[rnd() % i], v[i]);
    } 
}

const int N = 228228;

int a[N];

struct battle
{
    int L, R;
    vector<int> x;
    vector<int> y;
    int value;
    battle() {
        L = R = value = 0;
        x.clear(); y.clear();
    } 
    battle(vector<int> _x, vector<int> _y, int _value) {
        L = (int)x.size();
        R = (int)y.size();
        x = _x;
        y = _y;
        value = _value;
    }
};
bool operator<(battle a, battle b) {
    return a.value < b.value;
}
bool operator==(battle a, battle b) {
    return a.value == b.value;
}
bool used[N];
battle butt[N];
vector<int> list[N];

bool comp(int i, int j) {
    return butt[i] < butt[j] || (butt[i] == butt[j] && i < j);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
        used[a[i]] = 1;
    }
    int k;
    cin >> k;
    auto cmp = [](int a, int b) { return butt[a] < butt[b] || (butt[a] == butt[b] && a < b); };
    set<int, decltype(cmp)> st(cmp);
    for (int it = 1; it <= k; ++it) {
        int L, R;
        cin >> L >> R;
        vector<int> x(L), y(R);
        for (int i = 0; i < L; ++i) {
            cin >> x[i];
            list[x[i]].push_back(it);
        }
        for (int i = 0; i < R; ++i) {
            cin >> y[i];
        }
        int value = 0;
        for (int X : x) {
            value += (!used[X]);
        }
        butt[it] = battle(x, y, value);
        st.insert(it);
    }
    while (!st.empty()) {
        int indx = *st.begin();
        st.erase(indx);
        if (butt[indx].value > 0) break;
        for (int Y : butt[indx].y) {
            if (!used[Y]) {
                used[Y] = 1;
                for (int i : list[Y]) {
                    st.erase(i);
                    butt[i].value--;
                    st.insert(i);
                }
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        cnt += used[i];
    }
    cout << cnt << endl;
    for (int i = 1; i <= n; ++i) {
        if (used[i]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
    return 0;
}
// RU_023

/*
4 2
1 2
2
2 1
1 2
3
2 1
1 3
4


6 3
1 4 5
3
3 2
2 3 4
1 6
1 3
4
1 5 6
1 1
6
2


shironury

boootgslkfjdaojfdopsjfopjso
pgjq]pogjopsjg\qrwjopg
j
pogjqwrjgp]oqwjjqw]pjljfojpjowjow4jgopja    ohbip]aeo'rogpoaj0
[bkrw
pипустьбудетрукатвоятвердаojgqwjp\\j\;sync_with_stdiojp
ojeofmpworuc[owejgoprwig
[sdkz
pgj
p[gjes
p0ghjqsp[

jg
prsjgopjg]prwjgoprejgopjrepogjrepog]jgoprejgrgjporeqjgoperjgoprejgopeqrjgopeqrjgoprqwjgpoqjrwsopt4ng\ojsbjsoprnbfqsn\bvhqerpogjorwo
pwewh\rwh \wjiowe orw jop jgr\p jpj o jopj gr\pj p gjop j\pj\pe jp'oj [
 k
 p[eq   fj\pjfdwj\ejopjojopjopjf;'djpfsj, ipojs\p gpsdigsj gorkgjgjrogjdojgiao'fsdvopdshpdfidopcnweojccodj [cjd;ofjd[jdspmcojc"ajno[:Afvoq[w0shbprs`nm/jP{Vadmn;'fnc[Ajojsfpfjcffor 9int i= ; 1 < nfor (int i =1; for (int i =1 ; i <= n: ++i) frfor (int j = 1; j <= ml; ++'}]]]]]]]]]
5
1 5
1 2
2 3
2 
4
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20088 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20044 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19960 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19960 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20072 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20088 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 22572 KB Output is correct
2 Correct 808 ms 23648 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 26040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 28816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 29168 KB Time limit exceeded
2 Halted 0 ms 0 KB -