結果

問題 No.2643 Many Range Sums Problems
ユーザー ゆにぽけゆにぽけ
提出日時 2024-02-19 22:44:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,163 bytes
コンパイル時間 3,010 ms
コンパイル使用メモリ 143,616 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-02-19 22:44:39
合計ジャッジ時間 13,448 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 806 ms
6,676 KB
testcase_04 AC 624 ms
6,676 KB
testcase_05 AC 605 ms
6,676 KB
testcase_06 AC 900 ms
6,676 KB
testcase_07 AC 560 ms
6,676 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 479 ms
6,676 KB
testcase_11 AC 378 ms
6,676 KB
testcase_12 AC 297 ms
6,676 KB
testcase_13 AC 529 ms
6,676 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 610 ms
6,676 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 20 ms
6,676 KB
testcase_22 AC 67 ms
6,676 KB
testcase_23 AC 120 ms
6,676 KB
testcase_24 AC 217 ms
6,676 KB
testcase_25 AC 226 ms
6,676 KB
testcase_26 AC 19 ms
6,676 KB
testcase_27 AC 21 ms
6,676 KB
testcase_28 AC 1 ms
6,676 KB
testcase_29 AC 2 ms
6,676 KB
testcase_30 AC 578 ms
6,676 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

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();
}
0