Submission #1162988


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, A, B;
  int X[100], Y[100];
  int U[10], V[10];

  cin >> N;
  cin >> A;
  for(int i = 0; i < A; i++) {
    cin >> X[i] >> Y[i];
    --X[i], --Y[i];
  }
  cin >> B;
  for(int i = 0; i < B; i++) {
    cin >> U[i] >> V[i];
    --U[i], --V[i];
  }

  int ret = 0;
  for(int i = 0; i < 1 << B; i++) {
    set< int > need[100];
    bool v[100] = {};
    int proc = 0;

    for(int j = 0; j < A; j++) {
      need[X[j]].insert(Y[j]);
    }
    for(int k = 0; k < B; k++) {
      if((i >> k) & 1) {
        need[V[k]].insert(U[k]);
      } else {
        v[U[k]] = true;
      };
    }
    bool update = true;
    while(update) {
      update = false;
      for(int j = 0; j < N; j++) {
        if(!v[j] && need[j].empty()) {
          v[j] = true;
          update = true;
          ++proc;
          for(int k = 0; k < N; k++) need[k].erase(j);
        }
      }
    }
    ret = max(ret, proc);
  }

  cout << ret << endl;
}

Submission Info

Submission Time
Task C - ぬりまーす
User ei13333
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1042 Byte
Status
Exec Time 78 ms
Memory 256 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 x_sample_1.txt, x_sample_2.txt, x_sample_3.txt, x_sample_4.txt, x_sample_5.txt
All 100 / 100 corner1.txt, corner2.txt, corner3.txt, corner4.txt, manual1.txt, manual2.txt, manual3.txt, manual4.txt, manual5.txt, random1.txt, random10.txt, random11.txt, random12.txt, random13.txt, random14.txt, random15.txt, random2.txt, random3.txt, random4.txt, random5.txt, random6.txt, random7.txt, random8.txt, random9.txt, x_sample_1.txt, x_sample_2.txt, x_sample_3.txt, x_sample_4.txt, x_sample_5.txt
Case Name Status Exec Time Memory
corner1.txt 6 ms 256 KB
corner2.txt 6 ms 256 KB
corner3.txt 1 ms 256 KB
corner4.txt 1 ms 256 KB
manual1.txt 48 ms 256 KB
manual2.txt 76 ms 256 KB
manual3.txt 78 ms 256 KB
manual4.txt 2 ms 256 KB
manual5.txt 2 ms 256 KB
random1.txt 18 ms 256 KB
random10.txt 12 ms 256 KB
random11.txt 6 ms 256 KB
random12.txt 12 ms 256 KB
random13.txt 8 ms 256 KB
random14.txt 17 ms 256 KB
random15.txt 9 ms 256 KB
random2.txt 9 ms 256 KB
random3.txt 9 ms 256 KB
random4.txt 23 ms 256 KB
random5.txt 42 ms 256 KB
random6.txt 16 ms 256 KB
random7.txt 12 ms 256 KB
random8.txt 44 ms 256 KB
random9.txt 44 ms 256 KB
x_sample_1.txt 1 ms 256 KB
x_sample_2.txt 1 ms 256 KB
x_sample_3.txt 1 ms 256 KB
x_sample_4.txt 1 ms 256 KB
x_sample_5.txt 1 ms 256 KB