oj.uz

Submission #156577

# Submission time Handle Problem Language Result Execution time Memory
156577 2019-10-06T14:29:34 Z heon Alkemija (COCI18_alkemija) C++17
80 / 80
 83 ms 11608 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

const int maxn = 1e5 + 5;
vi g[maxn], cmp[maxn];
int deg[maxn], done[maxn], a[maxn];
vi res;

void dfs(int u){
  res.push_back(u);
  done[u] = 1;
  for(int v : g[u]){
    if(--deg[v] == 0){
      for(int y : cmp[v]){
        if(!done[y]){
          dfs(y);
        }
      }
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  int n, m;
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    cin >> a[i];
  }
  int k;
  cin >> k;
  for(int i = 0; i < k; i++){
    int l, r;
    cin >> l >> r;
    for(int j = 0; j < l; j++){
      int x;
      cin >> x;
      g[x].push_back(i);
    }
    for(int j = 0; j < r; j++){
      int x;
      cin >> x;
      cmp[i].push_back(x);
    }
    deg[i] = l;
  }
  for(int i = 0; i < m; i++){
    if(!done[a[i]]){
      dfs(a[i]);
    }
  }
  cout << res.size() << "\n";
  sort(all(res));
  for(int x : res){
    cout << x << " ";
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5088 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6820 KB Output is correct
2 Correct 31 ms 7540 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9160 KB Output is correct
2 Correct 58 ms 9972 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10872 KB Output is correct
2 Correct 68 ms 10104 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11608 KB Output is correct
2 Correct 71 ms 11220 KB Output is correct