Submission #23685

#	Time	Username	Problem	Language	Result	Execution time	Memory
23685		kdh9949	Toll (APIO13_toll)	C++14	16 / 100	0 ms	7888 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[300022], mi;
ll sp[22], a[22], cans;
vector<Edg> av, v, sv, t[100010], st[22];

struct Dsu{
	int p[100010];
	void ini(){
		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();
	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();
	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){
	a[x] = sp[x];
	for(auto &i : st[x]){
		if(chk[i.i]) continue;
        if(i.e == p) continue;
		ll t = adfs(i.e, x);
		a[x] += t;
		if(i.i > m) cans += (ll)i.c * t;
	}
	return a[x];
}

int gdfs(int x, int p, int e, int t, queue<int> &q){
	for(auto &i : st[x]){
        if(chk[i.i]) continue;
        if(i.e == p) continue;
        if(gdfs(i.e, x, e, t, q)){
            if(t == 0 && i.i <= m){
				if(!mi || av[mi - 1].c < i.c) mi = i.i;
            }
            else if(t == 1 && i.i > m){
				q.push(i.c);
				i.c = min(i.c, av[mi - 1].c);
            }
            else if(t == 2 && i.i > m){
				i.c = q.front();
				q.pop();
            }
			return 1;
        }
	}
	return (x == e);
}

ll btk(int x){
	if(x > k){ cans = 0; adfs(wh[1], 0); return cans; }
	ll ret = btk(x + 1);
	mi = 0;
	queue<int> q;
	gdfs(s[x], 0, e[x], 0, q);
	if(!mi) return ret;
	gdfs(s[x], 0, e[x], 1, q);
	st[s[x]].push_back({s[x], e[x], av[mi - 1].c, m + x});
	st[e[x]].push_back({e[x], s[x], av[mi - 1].c, m + x});
	chk[mi] = 1;
	ret = max(ret, btk(x + 1));
	chk[mi] = 0;
	st[s[x]].pop_back();
	st[e[x]].pop_back();
	gdfs(s[x], 0, e[x], 2, q);
	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, cnt = 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){
		int x = wh[i.s];
		int y = wh[i.e];
		st[x].push_back({x, y, i.c, i.i});
		st[y].push_back({y, x, i.c, i.i});
	}
	printf("%lld\n", btk(1));
}

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