結果

問題 No.3093 Safe Infection
ユーザー tnakao0123
提出日時 2025-04-09 10:41:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 91 ms / 2,000 ms
コード長 1,223 bytes
コンパイル時間 826 ms
コンパイル使用メモリ 61,104 KB
実行使用メモリ 14,224 KB
最終ジャッジ日時 2025-04-09 10:42:01
合計ジャッジ時間 6,209 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 70
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:35:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |   scanf("%d%d%d", &n, &m, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:36:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |   for (int i = 0; i < n; i++) scanf("%d", as + i);
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:40:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3093.cc:  No.3093 Safe Infection - yukicoder
 */

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

using namespace std;

/* constant */

const int MAX_N = 100000;
const int MAX_M = 100000;

/* typedef */

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

/* global variables */

int as[MAX_N];
pii ais[MAX_N];
spii ses[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; i++) scanf("%d", as + i);

  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    if (as[u] < as[v] || (as[u] == as[v] && u < v))
      ses[u].insert({as[v], v});
    else
      ses[v].insert({as[u], u});
  }

  for (int i = 0; i < n; i++) ais[i] = {as[i], i};
  sort(ais, ais + n);

  for (int i = 0; i < n - 1; i++) {
    auto [au, u] = ais[i];

    auto &seu = ses[u];
    if (seu.empty()) { puts("No"); return 0; }

    auto [av, v] = *seu.begin();
    seu.erase(seu.begin());
    if (av - au > k) { puts("No"); return 0; }

    auto &sev = ses[v];
    if (seu.size() > sev.size()) swap(seu, sev);
    for (auto &e: seu) sev.insert(e);
    seu.clear();
  }

  puts("Yes");
  return 0;
}
0