結果

問題 No.1014 competitive fighting
ユーザー Y17Y17
提出日時 2020-03-20 23:42:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 649 ms / 2,000 ms
コード長 3,565 bytes
コンパイル時間 2,279 ms
コンパイル使用メモリ 189,756 KB
実行使用メモリ 191,628 KB
最終ジャッジ日時 2024-07-07 12:56:28
合計ジャッジ時間 22,182 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
69,948 KB
testcase_01 AC 51 ms
69,944 KB
testcase_02 AC 62 ms
69,820 KB
testcase_03 AC 62 ms
69,944 KB
testcase_04 AC 63 ms
69,856 KB
testcase_05 AC 643 ms
128,352 KB
testcase_06 AC 646 ms
128,160 KB
testcase_07 AC 648 ms
128,232 KB
testcase_08 AC 647 ms
128,292 KB
testcase_09 AC 649 ms
128,352 KB
testcase_10 AC 635 ms
191,628 KB
testcase_11 AC 427 ms
112,964 KB
testcase_12 AC 639 ms
128,508 KB
testcase_13 AC 328 ms
97,408 KB
testcase_14 AC 290 ms
96,240 KB
testcase_15 AC 350 ms
99,084 KB
testcase_16 AC 60 ms
71,184 KB
testcase_17 AC 151 ms
81,588 KB
testcase_18 AC 544 ms
121,528 KB
testcase_19 AC 633 ms
127,592 KB
testcase_20 AC 246 ms
92,896 KB
testcase_21 AC 493 ms
120,932 KB
testcase_22 AC 375 ms
104,324 KB
testcase_23 AC 169 ms
85,584 KB
testcase_24 AC 182 ms
83,672 KB
testcase_25 AC 86 ms
72,932 KB
testcase_26 AC 483 ms
118,668 KB
testcase_27 AC 155 ms
81,532 KB
testcase_28 AC 160 ms
82,344 KB
testcase_29 AC 61 ms
70,236 KB
testcase_30 AC 612 ms
127,140 KB
testcase_31 AC 506 ms
119,800 KB
testcase_32 AC 61 ms
70,304 KB
testcase_33 AC 78 ms
72,388 KB
testcase_34 AC 381 ms
108,520 KB
testcase_35 AC 468 ms
113,592 KB
testcase_36 AC 350 ms
107,240 KB
testcase_37 AC 68 ms
71,072 KB
testcase_38 AC 296 ms
93,916 KB
testcase_39 AC 179 ms
82,112 KB
testcase_40 AC 290 ms
93,456 KB
testcase_41 AC 228 ms
90,212 KB
testcase_42 AC 459 ms
112,572 KB
testcase_43 AC 79 ms
72,392 KB
testcase_44 AC 426 ms
110,884 KB
testcase_45 AC 268 ms
92,148 KB
testcase_46 AC 93 ms
74,636 KB
testcase_47 AC 167 ms
81,340 KB
testcase_48 AC 372 ms
108,132 KB
testcase_49 AC 68 ms
71,004 KB
testcase_50 AC 437 ms
111,552 KB
testcase_51 AC 265 ms
92,240 KB
testcase_52 AC 68 ms
71,020 KB
testcase_53 AC 636 ms
128,132 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