oj.uz

Submission #128034

# Submission time Handle Problem Language Result Execution time Memory
128034 2019-07-10T10:44:06 Z sebinkim Toll (APIO13_toll) C++14
100 / 100
 2071 ms 12148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

struct edge{
	int u, v, c;
	
	edge() {}
	edge(int u, int v, int c) : u(u), v(v), c(c) {}
	
	bool operator < (const edge &e) const { return c < e.c; }
};

vector <edge> E, K;
vector <int> V;
int U1[101010], U2[101010];
ll C[101010];
vector <pii> T[44];
int P[44], U[44], D[44], Y[44], Z[44];
ll X[44], W[44];
int n, m, k, rt;
ll ans;

int find(int p) { return p == U[p]? p : U[p] = find(U[p]); }
int find1(int p) { return p == U1[p]? p : U1[p] = find1(U1[p]); }
int find2(int p) { return p == U2[p]? p : U2[p] = find2(U2[p]); }

ll dfs(int p, int r)
{
	P[p] = r; X[p] = W[p];
	
	for(pii &t: T[p]){
		if(t.first != r){
			Z[t.first] = t.second;
			D[t.first] = D[p] + 1;
			X[p] += dfs(t.first, p);
		}
	}
	
	return X[p];
}

int color(int p, int q, int c)
{
	if(p == q) return p;
	if(D[p] < D[q]) swap(p, q);
	if(U[p] == p){
		Y[p] = c;
		U[p] = color(P[p], q, c);
	}
	else U[p] = color(U[p], q, c);
}

int main()
{
	int i, j, u, v, c;
	ll s;
	
	scanf("%d%d%d", &n, &m, &k);
	
	for(i=0; i<m; i++){
		scanf("%d%d%d", &u, &v, &c);
		E.emplace_back(u, v, c);
	}
	
	sort(E.begin(), E.end());
	
	for(i=1; i<=n; i++){
		U1[i] = i;
	}
	
	for(edge &e: E){
		if(find1(e.u) != find1(e.v)){
			U1[find1(e.u)] = find1(e.v); 
		}
		else e.c = 1e9;
	}
	
	for(i=0; i<k; i++){
		scanf("%d%d", &u, &v);
		E.emplace_back(u, v, 0);
	}
	
	for(i=1; i<=n; i++){
		scanf("%lld", C + i);
	}
	
	sort(E.begin(), E.end());
	
	for(i=1; i<=n; i++){
		U1[i] = i; U2[i] = i;
	}
	
	for(edge &e: E){
		if(find1(e.u) != find1(e.v)){
			U1[find1(e.v)] = find1(e.u);
			if(e.c){
				C[find2(e.u)] += C[find2(e.v)];
				U2[find2(e.v)] = find2(e.u);
				e.c = 1e9;
			}
		}
	}
	
	sort(E.begin(), E.end());
	
	for(; E.back().c > 1e6; E.pop_back());
	
	for(i=1; i<=n; i++){
		if(find2(i) == i) V.push_back(i);
	}
	
	sort(V.begin(), V.end());
	
	for(i=0; i<V.size(); i++){
		W[i] = C[V[i]];
	}
	
	rt = lower_bound(V.begin(), V.end(), find2(1)) - V.begin();
	
	for(edge &e: E){
		e.u = lower_bound(V.begin(), V.end(), find2(e.u)) - V.begin();
		e.v = lower_bound(V.begin(), V.end(), find2(e.v)) - V.begin();
		if(e.u == e.v) for(; ; );
	}
	
	for(i=0; i<(1<<k); i++){
		K.clear();
		
		for(j=0; j<V.size(); j++){
			T[j].clear(); U[j] = j;
			X[j] = Y[j] = Z[j] = 0;
		}
		
		for(j=0; j<k; j++) if(i & (1 << j)){
			edge &e = E[j];
			if(find(e.u) != find(e.v)){
				U[find(e.u)] = find(e.v);
				T[e.u].emplace_back(e.v, 1);
				T[e.v].emplace_back(e.u, 1);
			}
			else break;
		}
		
		if(j < k) continue;
		
		for(; j<E.size(); j++){
			edge &e = E[j];
			if(find(e.u) != find(e.v)){
				U[find(e.u)] = find(e.v);
				T[e.u].emplace_back(e.v, 0);
				T[e.v].emplace_back(e.u, 0);
			}
			else K.push_back(e);
		}
		
		dfs(rt, rt);
		
		for(j=0; j<V.size(); j++){
			U[j] = j;
		}
		
		for(edge &e: K){
			color(e.u, e.v, e.c);
		}
		
		for(j=0, s=0; j<V.size(); j++){
			if(Z[j]) s += X[j] * Y[j];
		}
		
		ans = max(ans, s);
	}
	
	printf("%lld\n", ans);
	
	return 0;	
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++){
           ~^~~~~~~~~
toll.cpp:133:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<V.size(); j++){
            ~^~~~~~~~~
toll.cpp:150:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<E.size(); j++){
         ~^~~~~~~~~
toll.cpp:162:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<V.size(); j++){
            ~^~~~~~~~~
toll.cpp:170:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, s=0; j<V.size(); j++){
                 ~^~~~~~~~~
toll.cpp: In function 'int color(int, int, int)':
toll.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
toll.cpp: In function 'int main()':
toll.cpp:62: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:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", C + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 6 ms 732 KB Output is correct
6 Correct 6 ms 632 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 6 ms 732 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 310 ms 12144 KB Output is correct
8 Correct 311 ms 12148 KB Output is correct
9 Correct 305 ms 11992 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 6 ms 732 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 310 ms 12144 KB Output is correct
8 Correct 311 ms 12148 KB Output is correct
9 Correct 305 ms 11992 KB Output is correct
10 Correct 1672 ms 11992 KB Output is correct
11 Correct 2027 ms 12008 KB Output is correct
12 Correct 2071 ms 11992 KB Output is correct