結果
問題 | No.2643 Many Range Sums Problems |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:10:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,942 ms / 8,000 ms |
コード長 | 1,630 bytes |
コンパイル時間 | 2,124 ms |
コンパイル使用メモリ | 207,008 KB |
最終ジャッジ日時 | 2025-02-19 17:04:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long INF = 1000000000000000000;int main(){int N, K;cin >> N >> K;vector<int> R(N);vector<long long> X(N);for (int i = 0; i < N; i++){cin >> R[i] >> X[i];}for (int i = 0; i < N; i++){vector<vector<pair<long long, int>>> E(N + 1);for (int j = 0; j < N; j++){if (j != i){E[j].push_back(make_pair(X[j], R[j]));E[R[j]].push_back(make_pair(-X[j], j));}}int cnt = 0;vector<int> c(N + 1, -1);vector<long long> d(N + 1, 0);for (int j = 0; j <= N; j++){if (c[j] == -1){c[j] = cnt;queue<int> Q;Q.push(j);while (!Q.empty()){int v = Q.front();Q.pop();for (pair<long long, int> P : E[v]){int w = P.second;if (c[w] == -1){c[w] = cnt;d[w] = d[v] + P.first;Q.push(w);}}}cnt++;}}bool ok = true;long long mn = -INF, mx = INF;for (int j = 0; j < N; j++){if (c[j] == c[j + 1]){if (d[j + 1] - d[j] < 0 || d[j + 1] - d[j] > K){ok = false;}}if (c[j] == 0 && c[j + 1] == 1){mx = min(mx, K - d[j + 1] + d[j]);mn = max(mn, -d[j + 1] + d[j]);}if (c[j] == 1 && c[j + 1] == 0){mx = min(mx, d[j + 1] - d[j]);mn = max(mn, -K + d[j + 1] - d[j]);}}if (mn > mx){ok = false;}if (ok){cout << "Yes" << endl;} else {cout << "No" << endl;}}}