oj.uz

Submission #23686

# Submission time Handle Problem Language Result Execution time Memory
23686 2017-05-21T03:26:40 Z kdh9949 Toll (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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