oj.uz

답안 #901645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901645 2024-01-09T20:51:23 Z stefanneagu 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 0 ms 348 KB 
// 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); // ?
          q.push(i); // poate asa e mai stronck
          q.push(j);
          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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -