oj.uz

답안 #246987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246987 2020-07-10T17:14:44 Z patrikpavic2 통행료 (APIO13_toll) C++17
100 / 100
 2499 ms 21352 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
 
#define X first
#define Y second
#define PB push_back
 
using namespace std;
 
typedef long long ll;
typedef pair < int, int > pii;
 
const int N = 3e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
 
int n, m, k;
int u[N], v[N], tz[N], mra[N];
int pu[N], pv[N], par[N], rd[N];
int lg[M], dep[N], iznad[N], paar[N];
ll siz[N];
vector < int > vrati, stb;
vector < pii > g[N];
vector < int > za_pos;
 
bool cmp(int x, int y){
	return tz[x] < tz[y];
}
 
int pr(int x){
	if(par[x] == x) return x;
	return par[x] = pr(par[x]);
}
 
void mrg(int x, int y, bool posebno = 0){
	if(pr(x) == pr(y)) return;
	if(posebno){
		//printf("moram %d %d\n", x, y);
		//printf("prije %lld %lld\n", siz[pr(x)], siz[pr(y)]);
		siz[pr(x)] += siz[pr(y)];
	}
	par[pr(y)] = pr(x);
}
 
ll sol = 0, uk = 0;

void brzi_dfs(int x, int lst, int br){
	iznad[x] = br; paar[x] = lst;
	dep[x] = dep[lst] + 1;
	for(pii y : g[x])
		if(y.Y != lst)
			brzi_dfs(y.Y, x, y.X);
}

ll dfs(int x, int lst){
	ll ret = siz[x];
	for(pii y : g[x]){
		if(y.Y == lst) continue;
		ll vel = dfs(y.Y, x);
		if(y.X >= m)
			sol += vel * tz[y.X];
		ret += vel;
	}
	return ret;
}
 
bool nadi_put(int cur, int en, int lst, int gran){
	if(cur == en)
		return 1;
	for(pii nxt : g[cur]){
		if(nxt.Y == lst) continue;
		if(nadi_put(nxt.Y, en, cur, gran)){
			tz[nxt.X] = min(tz[nxt.X], gran);
			return 1;
		}
	}
	return 0;
}
 
int main(){
	for(int i = 0;i < 20;i++)
		lg[(1 << i)] = i;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1;i <= n;i++)
		par[i] = i;
	for(int i = 0;i < m;i++){
		scanf("%d%d%d", u + i, v + i, tz + i);
		rd[i] = i;
	}
	sort(rd, rd + m, cmp);
	for(int i = 0;i < k;i++){
		scanf("%d%d", pu + i, pv + i);
		mrg(pu[i], pv[i]);
	}
	for(int i = 0;i < m;i++){
		if(pr(u[rd[i]]) != pr(v[rd[i]])){
			mra[rd[i]] = 1; mrg(u[rd[i]], v[rd[i]]);
		}
	}
	for(int i = 1;i <= n;i++)
		par[i] = i;
	for(int i = 0;i < m;i++){
		if(mra[i]) mrg(u[i], v[i]);
	}
	for(int i = 0;i < m;i++){
		if(pr(u[rd[i]]) != pr(v[rd[i]])){
			stb.PB(rd[i]); mrg(u[rd[i]], v[rd[i]]);
		}
	}
	for(int i = 1;i <= n;i++){
		par[i] = i; scanf("%lld", siz + i);
		uk += siz[i];
	}
	for(int i = 0;i < m;i++){
		if(mra[i]) mrg(u[i], v[i], 1);
	}
	for(int i = 1;i <= n;i++)
		if(par[i] == i)
			vrati.PB(i);
	for(int x : stb)
		u[x] = pr(u[x]), v[x] = pr(v[x]);
	for(int i = 0;i < k;i++)
		pu[i] = pr(pu[i]), pv[i] = pr(pv[i]);
	ll ans = 0;
	int root = pr(1);
	//printf("tu sam\n");
	//for(int x : vrati)
	//	printf("cvor %d vel %lld\n", x, siz[x]);
	//printf("root = %d\n", root);
	for(int msk = 0;msk < (1 << k);msk++){
		for(int x : vrati)
			par[x] = x, g[x].clear();
		bool dobar = 1;
		for(int i = 0;i < k;i++){
			if((1 << i) & msk){
				if(pr(pu[i]) == pr(pv[i])){
					dobar = 0; break;
				}
				mrg(pu[i], pv[i]);
				g[pu[i]].PB({m + i, pv[i]});
				g[pv[i]].PB({m + i, pu[i]});
				tz[m + i] = INF;
			}
		}
		if(!dobar) break;
		for(int x : stb){
			if(pr(u[x]) == pr(v[x])){
				za_pos.PB(x);
				continue;
			}
			mrg(u[x], v[x]);			
			g[u[x]].PB({x, v[x]});
			g[v[x]].PB({x, u[x]});
		}
		brzi_dfs(root, root, m + k);
		for(int x : za_pos){
			int A = u[x], B = v[x];
			while(dep[A] > dep[B])
				tz[iznad[A]] = min(tz[iznad[A]], tz[x]), A = paar[A];
			while(dep[A] < dep[B])
				tz[iznad[B]] = min(tz[iznad[B]], tz[x]), B = paar[B];		
			while(A != B){
				tz[iznad[A]] = min(tz[iznad[A]], tz[x]), A = paar[A];
				tz[iznad[B]] = min(tz[iznad[B]], tz[x]), B = paar[B];		
			}
				
		}
		za_pos.clear();
		sol = 0; dfs(root, root);
		ans = max(ans, sol);
	}
	printf("%lld\n", ans);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:84:7: 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:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", u + i, v + i, tz + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", pu + i, pv + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:112:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   par[i] = i; scanf("%lld", siz + i);
               ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 300 ms 14704 KB Output is correct
8 Correct 298 ms 14712 KB Output is correct
9 Correct 290 ms 14808 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 12 ms 7552 KB Output is correct
6 Correct 12 ms 7680 KB Output is correct
7 Correct 300 ms 14704 KB Output is correct
8 Correct 298 ms 14712 KB Output is correct
9 Correct 290 ms 14808 KB Output is correct
10 Correct 2013 ms 14840 KB Output is correct
11 Correct 2438 ms 14748 KB Output is correct
12 Correct 2499 ms 21352 KB Output is correct