結果

問題 No.1014 competitive fighting
ユーザー Y17Y17
提出日時 2020-03-20 23:42:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 639 ms / 2,000 ms
コード長 3,565 bytes
コンパイル時間 2,411 ms
コンパイル使用メモリ 187,384 KB
実行使用メモリ 192,868 KB
最終ジャッジ日時 2023-09-21 19:22:41
合計ジャッジ時間 22,149 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
74,076 KB
testcase_01 AC 40 ms
74,080 KB
testcase_02 AC 42 ms
74,040 KB
testcase_03 AC 41 ms
73,924 KB
testcase_04 AC 40 ms
74,036 KB
testcase_05 AC 620 ms
134,128 KB
testcase_06 AC 623 ms
134,516 KB
testcase_07 AC 619 ms
134,260 KB
testcase_08 AC 619 ms
133,968 KB
testcase_09 AC 620 ms
134,472 KB
testcase_10 AC 639 ms
192,868 KB
testcase_11 AC 418 ms
116,604 KB
testcase_12 AC 604 ms
134,436 KB
testcase_13 AC 290 ms
100,780 KB
testcase_14 AC 273 ms
99,712 KB
testcase_15 AC 316 ms
104,628 KB
testcase_16 AC 49 ms
75,068 KB
testcase_17 AC 136 ms
85,244 KB
testcase_18 AC 508 ms
127,884 KB
testcase_19 AC 593 ms
133,504 KB
testcase_20 AC 226 ms
96,300 KB
testcase_21 AC 464 ms
125,636 KB
testcase_22 AC 358 ms
107,556 KB
testcase_23 AC 164 ms
87,428 KB
testcase_24 AC 168 ms
87,604 KB
testcase_25 AC 69 ms
77,000 KB
testcase_26 AC 466 ms
125,596 KB
testcase_27 AC 139 ms
85,296 KB
testcase_28 AC 147 ms
86,496 KB
testcase_29 AC 45 ms
74,356 KB
testcase_30 AC 595 ms
132,788 KB
testcase_31 AC 482 ms
126,732 KB
testcase_32 AC 45 ms
74,228 KB
testcase_33 AC 64 ms
76,368 KB
testcase_34 AC 365 ms
113,256 KB
testcase_35 AC 459 ms
119,168 KB
testcase_36 AC 344 ms
111,412 KB
testcase_37 AC 51 ms
75,228 KB
testcase_38 AC 293 ms
96,648 KB
testcase_39 AC 162 ms
85,612 KB
testcase_40 AC 277 ms
96,308 KB
testcase_41 AC 216 ms
93,140 KB
testcase_42 AC 437 ms
116,660 KB
testcase_43 AC 61 ms
76,424 KB
testcase_44 AC 405 ms
114,788 KB
testcase_45 AC 247 ms
94,892 KB
testcase_46 AC 78 ms
78,372 KB
testcase_47 AC 153 ms
85,248 KB
testcase_48 AC 352 ms
113,376 KB
testcase_49 AC 53 ms
75,208 KB
testcase_50 AC 423 ms
115,460 KB
testcase_51 AC 254 ms
94,944 KB
testcase_52 AC 53 ms
75,064 KB
testcase_53 AC 621 ms
134,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

vector<vector<int>> graph(500010);

vector<int> seg;
using UnWeightedGraph = vector< vector< int > >;

int num[500010];
int n;
template< typename G >
struct StronglyConnectedComponents {
  const G &g;
  UnWeightedGraph gg, rg;
  vector< int > comp, order, used;

  StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
    for(int i = 0; i < g.size(); i++) {
      for(auto e : g[i]) {
        gg[i].emplace_back((int) e);
        rg[(int) e].emplace_back(i);
      }
    }
  }

  int operator[](int k) {
    return comp[k];
  }

  void dfs(int idx) {
    if(used[idx]) return;
    used[idx] = true;
    for(int to : gg[idx]) dfs(to);
    order.push_back(idx);
  }

  void rdfs(int idx, int cnt) {
    if(comp[idx] != -1) return;
    comp[idx] = cnt;
    for(int to : rg[idx]) rdfs(to, cnt);
  }

  void build(UnWeightedGraph &t) {
    for(int i = 0; i < gg.size(); i++) dfs(i);
    reverse(begin(order), end(order));
    int ptr = 0;
    for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++;

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      for(auto &to : g[i]) {
        int x = comp[i], y = comp[to];
        if(x == y) continue;
        t[x].push_back(y);
      }
    }
  }
};

int size;
int init(int n){
	int sz = n;
	size = 1; while(size < sz) size *= 2;
	int si = n;
	seg.resize(2*size);
	for(int i = 0;i < size;i++){
		seg[i+size-1] = si;
		if(i < n) graph[si].push_back(i);
		si++;
	}

	for(int i = size-2;i >= 0;i--){
		seg[i] = si;
		graph[si].push_back(seg[i*2+1]);
		graph[si].push_back(seg[i*2+2]);
		si++;
	}
	return si;
}

void add_edge(int a, int b, int num, int k=0, int l=0, int r=size){
	if(r <= a || b <= l) return;
	if(a <= l && r <= b) {
		graph[num].push_back(seg[k]);
		return;
	}

	add_edge(a, b, num, 2*k+1, l, (l+r)/2); 
	add_edge(a, b, num, 2*k+2, (l+r)/2, r); 
}

vector<vector<int>> ngraph;
int cnt[1000010];

int memo[1000010];

int dp(int idx){
	if(cnt[idx] > 2){
		return LLONG_MAX;
	}
	if(memo[idx] != -1) return memo[idx];

	int ans = num[idx];
	for(int i = 0;i < ngraph[idx].size();i++){
		int tmp = dp(ngraph[idx][i]);
		if(tmp == LLONG_MAX) return memo[idx] = tmp;
		ans = max(ans, tmp+num[idx]);
	}
	return memo[idx] = ans;
}

signed main(){
	cin >> n;

	vector<pair<int, pair<int, int>>> p, konbo;
	vector<int> aa;

	int all_n = init(n);

	for(int i = 0;i < n;i++){
		int a, b, c;
		cin >> a >> b >> c;
		p.push_back({a, {b, c}});
		konbo.push_back({a, {b, c}});
		aa.push_back(a);
	}

	sort(p.begin(), p.end());
	sort(aa.begin(), aa.end());

	for(int i = 0;i < n;i++){
		int idx = upper_bound(aa.begin(), aa.end(), p[i].second.first-p[i].second.second) - aa.begin();
		if(idx <= i){
			add_edge(0, idx, i);
		}else{
			add_edge(0, i, i);
			add_edge(i+1, idx, i);
		}
	}

	StronglyConnectedComponents<vector<vector<int>>> kyo(graph);
	kyo.build(ngraph);

	for(int i = 0;i < all_n;i++){
		cnt[kyo[i]]++;
	}

	for(int i = 0;i < n;i++){
		int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin();
		num[kyo[idx]] = p[idx].second.first;
	}

	memset(memo, -1, sizeof(memo));

	for(int i = 0;i < n;i++){
		int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin();
		int ans = dp(kyo[idx]);
		if(ans == LLONG_MAX){
			cout << "BAN" << endl;
		}else{
			cout << ans << endl;
		}
	}
	
	return 0;
}
0