oj.uz

답안 #23686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23686 2017-05-21T03:26:40 Z kdh9949 통행료 (APIO13_toll) C++14
100 / 100
 1696 ms 24696 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct Edg{
	int s, e, c, i;
	bool operator<(const Edg &oth) const {
		return c < oth.c;
	}
};

int n, m, k, s[21], e[21], p[100010], wh[100010], ch[300022], chk[22], par[22], pc[22], dep[22], mi, cnt;
ll sp[22], a[22], ans;
vector<Edg> av, v, sv, t[100010], st[22], nv;

struct Dsu{
	int p[100010];
	void ini(int n){
		for(int i = 1; i <= n; i++) p[i] = i;
	}
	int fnd(int x){ return p[x] = (x == p[x] ? x : fnd(p[x])); }
	void uni(int x, int y){ p[fnd(x)] = fnd(y); }
} D;

void bld(){
	sort(v.begin(), v.end());
	D.ini(n);
	for(auto &i : v){
		if(D.fnd(i.s) == D.fnd(i.e)) continue;
		D.uni(i.s, i.e);
		t[i.s].push_back(i);
		t[i.e].push_back({i.e, i.s, i.c, i.i});
		ch[i.i] = 1;
	}
	for(int i = 1; i <= k; i++) v.push_back({s[i], e[i], 0, m + i});
	sort(v.begin(), v.end());
	D.ini(n);
	for(auto &i : v){
		if(D.fnd(i.s) == D.fnd(i.e)) continue;
		D.uni(i.s, i.e);
		if(ch[i.i]) ch[i.i] = 0;
	}
	for(int i = 1; i <= m; i++) if(ch[i]) sv.push_back(av[i - 1]);
}

void sdfs(int x, int pv, int id){
	wh[x] = id;
	sp[id] += (ll)p[x];
	for(auto &i : t[x]){
		if(i.e == pv) continue;
		if(ch[i.i]) continue;
		sdfs(i.e, x, id);
	}
}

ll adfs(int x, int p, int d){
	a[x] = sp[x];
	dep[x] = d;
	for(auto &i : st[x]){
        if(i.e == p) continue;
		a[x] += adfs(i.e, x, d + 1);
		par[i.e] = x;
		pc[i.e] = 1e9;
		chk[i.e] = i.i;
	}
	return a[x];
}

ll f(int x){
	D.ini(cnt);
	for(int i = 1; i <= cnt; i++) st[i].clear();
	nv.clear();
	for(int i = 1; i <= k; i++){
        if(x & (1 << (i - 1))){
            if(D.fnd(s[i]) == D.fnd(e[i])) return 0;
            D.uni(s[i], e[i]);
			st[s[i]].push_back({s[i], e[i], 0, 1});
			st[e[i]].push_back({e[i], s[i], 0, 1});
        }
	}
	for(auto &i : sv){
        if(D.fnd(i.s) == D.fnd(i.e)) nv.push_back(i);
        else{
			D.uni(i.s, i.e);
			st[i.s].push_back({i.s, i.e, 0, 0});
			st[i.e].push_back({i.e, i.s, 0, 0});
        }
	}
	adfs(1, 0, 0);
	for(auto &i : nv){
		if(dep[i.s] < dep[i.e]) swap(i.s, i.e);
        while(dep[i.s] != dep[i.e]){
			pc[i.s] = min(pc[i.s], i.c);
			i.s = par[i.s];
        }
        while(i.s != i.e){
			pc[i.s] = min(pc[i.s], i.c);
			pc[i.e] = min(pc[i.e], i.c);
			i.s = par[i.s]; i.e = par[i.e];
        }
	}
	ll ret = 0;
	for(int i = 2; i <= cnt; i++){
		if(chk[i]) ret += pc[i] * a[i];
	}
	return ret;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1, x, y, c; i <= m; i++){
		scanf("%d%d%d", &x, &y, &c);
		v.push_back({x, y, c, i});
	}
	av = v;
	for(int i = 1; i <= k; i++){
		scanf("%d%d", s + i, e + i);
	}
	for(int i = 1; i <= n; i++) scanf("%d", p + i);
	bld();
	for(int i = 1; i <= n; i++){
		if(!wh[i]){
			sdfs(i, 0, ++cnt);
		}
	}
	for(int i = 1; i <= k; i++){ s[i] = wh[s[i]]; e[i] = wh[e[i]]; }
	for(auto &i : sv){
		i.s = wh[i.s];
		i.e = wh[i.e];
	}
	sort(sv.begin(), sv.end());
	for(int i = 1; i <= (1 << k); i++) ans = max(ans, f(i));
	printf("%lld\n", ans);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:111:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
                             ^
toll.cpp:113:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c);
                              ^
toll.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", s + i, e + i);
                              ^
toll.cpp:120:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", p + i);
                                                ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6720 KB Output is correct
2 Correct 0 ms 6720 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6720 KB Output is correct
2 Correct 0 ms 6720 KB Output is correct
3 Correct 0 ms 6720 KB Output is correct
4 Correct 0 ms 6720 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6720 KB Output is correct
2 Correct 0 ms 6720 KB Output is correct
3 Correct 0 ms 6720 KB Output is correct
4 Correct 0 ms 6720 KB Output is correct
5 Correct 0 ms 7060 KB Output is correct
6 Correct 0 ms 7060 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6720 KB Output is correct
2 Correct 0 ms 6720 KB Output is correct
3 Correct 0 ms 6720 KB Output is correct
4 Correct 0 ms 6720 KB Output is correct
5 Correct 0 ms 7060 KB Output is correct
6 Correct 0 ms 7060 KB Output is correct
7 Correct 329 ms 24696 KB Output is correct
8 Correct 339 ms 24696 KB Output is correct
9 Correct 339 ms 24696 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6720 KB Output is correct
2 Correct 0 ms 6720 KB Output is correct
3 Correct 0 ms 6720 KB Output is correct
4 Correct 0 ms 6720 KB Output is correct
5 Correct 0 ms 7060 KB Output is correct
6 Correct 0 ms 7060 KB Output is correct
7 Correct 329 ms 24696 KB Output is correct
8 Correct 339 ms 24696 KB Output is correct
9 Correct 339 ms 24696 KB Output is correct
10 Correct 1289 ms 24696 KB Output is correct
11 Correct 1696 ms 24696 KB Output is correct
12 Correct 1649 ms 24696 KB Output is correct