結果

問題 No.3103 Butterfly Effect
コンテスト
ユーザー tnakao0123
提出日時 2025-04-14 14:15:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 519 ms / 5,000 ms
コード長 1,497 bytes
コンパイル時間 1,177 ms
コンパイル使用メモリ 69,940 KB
実行使用メモリ 66,304 KB
最終ジャッジ日時 2025-04-14 14:15:51
合計ジャッジ時間 23,858 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:36:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |   scanf("%d%d", &n, &qn);
      |   ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%d%d%d", ps + i, xs + i, ys + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3103.cc:  No.3103 Butterfly Effect - yukicoder
 */

#include<cstdio>
#include<set>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 400000;
const int MAX_QN = 400000;

/* typedef */

using pii = pair<int,int>;
using spii = set<pii>;

/* global variables */

int ps[MAX_QN], xs[MAX_QN], ys[MAX_QN];
int qs[MAX_QN], ts[MAX_N];
spii evs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, qn;
  scanf("%d%d", &n, &qn);
  for (int i = 0; i < qn; i++) {
    scanf("%d%d%d", ps + i, xs + i, ys + i);
    ps[i]--, xs[i]--, ys[i]--;
  }

  fill(ts, ts + n, qn);
  ts[0] = -1;
  int cnt = 1;

  for (int i = 0; i < qn; i++) {
    int pi = ps[i], xi = xs[i], yi = ys[i];

    if (ts[xi] < pi && ts[yi] < pi) {
      printf("%d\n", cnt);
      continue;
    }

    if (ts[xi] > pi && ts[yi] > pi) {
      evs[xi].insert({pi, yi});
      evs[yi].insert({pi, xi});
      printf("%d\n", cnt);
      continue;
    }

    if (ts[xi] > pi) swap(xi, yi);
    if (ts[yi] >= qn) cnt++;
    ts[yi] = pi;

    priority_queue<pii> q;
    q.push({-pi, yi});

    while (! q.empty()) {
      auto [pu, u] = q.top(); q.pop();
      pu = -pu;

      auto sit = evs[u].lower_bound({pu, -1});
      while (sit != evs[u].end()) {
	auto [pv, v] = *sit;
	if (ts[v] > pv) {
	  if (ts[v] >= qn) cnt++;
	  ts[v] = pv;
	  q.push({-pv, v});
	}
	sit = evs[u].erase(sit);
      }
    }

    printf("%d\n", cnt);
  }
  
  return 0;
}
0