oj.uz

답안 #557890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557890 2022-05-06T09:14:51 Z 600Mihnea 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 6 ms 7252 KB 
#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

const int N=100000+7;
int n;
int m;
int sol;
vector<int> g[N];
vector<int> ig[N];
vector<int> fl[N];
set<pair<int, int>> edges;

void add_g(int a, int b);
void add_fl(int a, int b);

void add_g(int a,int b){
  if(a==b||edges.count({a, b})) return;
  sol++;
  assert(a!=b);
  assert(1<=a&&a<=n);
  assert(1<=b&&b<=n);
  assert(!edges.count({a, b}));
  edges.insert({a, b});
  g[a].push_back(b);
  ig[b].push_back(a);
  if(edges.count({b, a})) {
    add_fl(a,b);
  }

  vector<int> cs;

  for (auto &c:fl[b]) {
    if(a!=c&&!edges.count({a, c})) {
      cs.push_back(c);
    }
  }
  for (auto &c:cs){
    add_g(a,c);
  }
}

void add_fl(int a,int b) {
  assert(a!=b);
  assert(1<=a&&a<=n);
  assert(1<=b&&b<=n);
  fl[a].push_back(b);
  fl[b].push_back(a);
  vector<int> bs,as;
  for (auto &inv:ig[a]) {
    if(inv!=b&&!edges.count({inv, b})) {
      assert(1<=b&&b<=n);
     /// add_g(inv, b);
      bs.push_back(inv);
    }
  }
  for (auto &inv:ig[b]) {
    if(inv!=a&&!edges.count({inv, a})) {
      assert(1<=a&&a<=n);
     /// add_g(inv, a);
      as.push_back(inv);
    }
  }
  for(auto &inv:bs) add_g(inv,b);
  for(auto &inv:as) add_g(inv,a);
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

 /// home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }


  cin>>n>>m;

  for (int im=1;im<=m;im++) {
    int a, b;
    cin>>a>>b;
    assert(1<=b&&b<=n);
    add_g(a,b);
    cout<<sol<<"\n";
  }
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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