CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1443993

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 4005;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

int n, m;
vector<pi> gph[MAXN];
vector<edg> ed;
int dep[MAXN], par[12][MAXN], pva[12][MAXN];

void dfs(int x, int p){
	for(auto &i : gph[x]){
		if(i.second == p) continue;
		par[0][i.second] = x;
		pva[0][i.second] = i.first;
		dep[i.second] = dep[x] + 1;
		dfs(i.second, x);
	}
}

int get(int s, int e){
	if(dep[e] < dep[s]) swap(s, e);
	int dx = dep[e] - dep[s];
	int ans = 0;
	for(int i=0; i<12; i++){
		if((dx >> i) & 1){
			ans = max(ans, pva[i][e]);
			e = par[i][e];
		}
	}
	for(int i=11; i>=0; i--){
		if(par[i][s] != par[i][e]){
			ans = max({ans, pva[i][s], pva[i][e]});
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s != e){
		ans = max({ans, pva[0][s], pva[0][e]});
	}
	return ans;
}

int main(){
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		ed.push_back({s, e, x});
	}
	sort(ed.begin(), ed.end());
	lint ans = 0;
	disj.init(n);
	for(auto &i : ed){
		if(disj.uni(i.s, i.e)){
			ans += i.x;
			gph[i.s].push_back(pi(i.x, i.e));
			gph[i.e].push_back(pi(i.x, i.s));
		}
	}
	dfs(1, 0);
	for(int i=1; i<12; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
			pva[i][j] = max(pva[i-1][j], pva[i-1][par[i-1][j]]);
		}
	}
	int q;
	scanf("%d",&q);
	while(q--){
		int s, e;
		scanf("%d %d",&s,&e);
		printf("%lld\n", ans - get(s, e));
	}
}

Submission

Task問題 A - グラフ / Graph
User nameユーザ名 koosaga
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1927 Byte
File nameファイル名
Exec time実行時間 177 ms
Memory usageメモリ使用量 8560 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
^
./Main.cpp:95:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:98:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s,&e);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 200 / 200 sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 300 / 300 sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt
All 200 / 200 sample_1.txt,sample_2.txt,sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 1 ms 384 KB
sample_2.txt AC 1 ms 384 KB
subtask_1_1.txt AC 2 ms 512 KB
subtask_1_10.txt AC 67 ms 3572 KB
subtask_1_11.txt AC 1 ms 384 KB
subtask_1_2.txt AC 15 ms 1400 KB
subtask_1_3.txt AC 133 ms 7408 KB
subtask_1_4.txt AC 3 ms 896 KB
subtask_1_5.txt AC 4 ms 896 KB
subtask_1_6.txt AC 34 ms 2040 KB
subtask_1_7.txt AC 132 ms 8176 KB
subtask_1_8.txt AC 3 ms 896 KB
subtask_1_9.txt AC 5 ms 960 KB
subtask_2_1.txt AC 134 ms 7024 KB
subtask_2_2.txt AC 133 ms 8176 KB
subtask_2_3.txt AC 134 ms 6896 KB
subtask_2_4.txt AC 134 ms 6640 KB
subtask_2_5.txt AC 4 ms 1024 KB
subtask_2_6.txt AC 10 ms 1148 KB
subtask_2_7.txt AC 36 ms 2040 KB
subtask_2_8.txt AC 133 ms 8432 KB
subtask_3_1.txt AC 171 ms 8432 KB
subtask_3_2.txt AC 177 ms 7532 KB
subtask_3_3.txt AC 41 ms 2304 KB
subtask_3_4.txt AC 45 ms 2240 KB
subtask_3_5.txt AC 106 ms 4336 KB
subtask_3_6.txt AC 140 ms 7152 KB
subtask_3_7.txt AC 172 ms 7792 KB
subtask_3_8.txt AC 171 ms 8560 KB