結果

問題 No.2643 Many Range Sums Problems
ユーザー ゆにぽけ
提出日時 2024-02-19 22:44:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,163 bytes
コンパイル時間 1,911 ms
コンパイル使用メモリ 138,812 KB
最終ジャッジ日時 2025-02-19 17:25:18
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 23 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cmath>
#include<numeric>
#include<iomanip>
using namespace std;
template<class T>
struct WeightedUnionFind{
vector<int> par,siz;
vector<T> diff_weight;
WeightedUnionFind(int n)
{
par.resize(n),siz.assign(n,1),diff_weight.resize(n);
iota(par.begin(),par.end(),0);
}
int root(int x)
{
if(par[x] == x) return x;
root(par[x]);
diff_weight[x] += diff_weight[par[x]];
return par[x] = root(par[x]);
}
T weight(int x)
{
root(x);
return diff_weight[x];
}
bool same(int x,int y)
{
return root(x) == root(y);
}
bool unite(int x,int y,T w)
{
w += weight(x); w -= weight(y);
x = root(x); y = root(y);
if(x == y) return false;
if(siz[x] < siz[y]) swap(x,y),w *= -1;
par[y] = x;
siz[x] += siz[y];
diff_weight[y] = w;
return true;
}
int size(int x)
{
return siz[root(x)];
}
T diff(int x,int y)
{
assert(same(x,y));
return weight(y)-weight(x);
}
};
/* int main() */
/* { */
/* ios::sync_with_stdio(false); */
/* cin.tie(nullptr); */
/* int n,m; */
/* cin >> n >> m; */
/* WeightedUnionFind<long long> uf(n); */
/* for(int i = 0;i < m;i++) */
/* { */
/* int l,r,d; */
/* cin >> l >> r >> d; */
/* l--; r--; */
/* if(uf.same(l,r)) */
/* { */
/* long long diff = uf.diff(l,r); */
/* if(diff != d) */
/* { */
/* cout << "No" << endl; */
/* return 0; */
/* } */
/* } */
/* else */
/* { */
/* uf.unite(l,r,d); */
/* } */
/* } */
/* cout << "Yes" << endl; */
/* } */
void 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++)
{
if(X[i] > (long long) (R[i] - i) * K)
{
cout << "No\n";
return;
}
}
for(int i = 0;i < N;i++)
{
WeightedUnionFind<long long> uf(N + 1);
for(int j = 0;j < N;j++)
{
if(j == i)
{
continue;
}
uf.unite(j,R[j],X[j]);
}
bool check = true;
for(int j = 0;j < N;j++)
{
if(uf.same(j,j + 1))
{
long long d = uf.diff(j,j + 1);
if(0 <= d && d <= K);
else
{
check = false;
break;
}
}
}
cout << (check ? "Yes\n":"No\n");
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
/* cin >> tt; */
while(tt--) Main();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0