제출 #901641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901641		stefanneagu	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	1 ms	348 KiB

joitter2

// subtask 1 - 1 punct

// brute? cred ca e chiar mai rau ca brute

// sum(n ^ 4) < 50 ^ 5 = 5 sec

// dar folosesc bitset! deci intra

#include <bits/stdc++.h>

using namespace std;

bitset<51> f[51]; // poate intra si subtask 2? :pleading_face:
int n;

int testcase(int loc) {
  bitset<51> curr[51];
  int ans = 0;
  queue<int> q;
  for(int i = 1; i <= n; i ++) {
    q.push(i);
    for(int j = 1; j <= n; j ++) {
      curr[i][j] = f[i][j];
    }
  }
  while(!q.empty()) {
    int i = q.front();
    q.pop();
    for(int j = 1; j <= n; j ++) {
      if(!curr[i][j]) {
        continue;
      }
      for(int k = 1; k <= n; k ++) {
        if(k == i || k == j) {
          continue;
        }
        // i e inter point
        if(!curr[i][k] && curr[j][k] && curr[k][j]) {
          // e posibil
          // sa vedeim in ce directii
          curr[i][k] = 1;
          q.push(k); // ?
          ans ++;
        }
      }
    }
  }
  return ans;
}

int main() {
  int m;
  cin >> n >> m;
  for(int i = 1; i <= m; i ++) {
    int a, b;
    cin >> a >> b;
    f[a][b] = 1;
    cout << testcase(i) + i << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83