Submission #23686

#	Time	Username	Problem	Language	Result	Execution time	Memory
23686		kdh9949	Toll (APIO13_toll)	C++14	100 / 100	1696 ms	24696 KiB

toll

#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 (stderr)

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22