oj.uz

답안 #257720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257720 2020-08-04T15:46:33 Z davooddkareshki 통행료 (APIO13_toll) C++17
78 / 100
 2500 ms 12136 KB 
#include<bits/stdc++.h>

using namespace std;
 
//#define int long long
#define F first 
#define S second 
#define pii pair<int,int> 
#define mpr make_pair

typedef long long ll;

const int maxn = 1e5+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;

int n, m, k;

struct dsu
{
	int par[maxn];
	void f_reset() {memset(par, -1, sizeof par);}
	void reset() {for(int i = 0; i <= 22; i++) par[i] = -1;}	
	
	int get_par(int v)
	{
		if(par[v] < 0) return v;
		return par[v] = get_par(par[v]);		
	}
	
	void add(int u, int v)
	{
		u = get_par(u);
		v = get_par(v);
		
		if(u == v) return;
		if(par[u] < par[v]) swap(u,v);
		par[v] += par[u];
		par[u] = v;
	}
	
	bool ask(int u, int v) {return (get_par(u) == get_par(v));}
} dsu;

vector<int> T[maxn];
ll sz[maxn];
int par[maxn], num, comp[maxn], p[maxn]; 
bool mark[maxn];

void dfs(int v)
{
	mark[v] = 1;
	comp[v] = num; sz[num] += p[v];
	for(auto u : T[v])
		if(!mark[u]) dfs(u);
}

vector<int> Tree[25];
int pa[maxn], W[maxn];
ll stt[maxn];
void dfs_T(int v)
{
	W[v] = inf;
	stt[v] = sz[v];
	for(auto u : Tree[v])
		if(u != pa[v])
		{
			pa[u] = v;
			dfs_T(u);
			stt[v] += stt[u];
		}
}

ll ans = 0;
void reset() 
{
	ans = 0;
	dsu.reset(); 
	for(int i = 0; i <= 22; i++) 
	{
		Tree[i].clear();
		W[i] = inf;
		pa[i] = 0;
		stt[i] = 0;
	}
}

signed main()
{
	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	
	scanf("%d%d%d", &n, &m, &k);	
	vector<pair<int,pii>> edge, Bedge; vector<pii> Redge;
	for(int i = 1, u, v, c; i <= m; i++)
	{
		scanf("%d%d%d", &u, &v, &c);
		edge.push_back({c,{u,v}});
	}		
	sort(edge.begin(), edge.end());
	
	dsu.f_reset();
	vector<pair<int,pii>> mst;
	for(auto e : edge)
	{
		int u = e.S.F, v = e.S.S;
		if(!dsu.ask(u,v))
		{
			dsu.add(u,v);
			mst.push_back(e);
		}
	}

	dsu.f_reset();
	for(int i = 1, u, v; i <= k; i++)
	{
		cin>> u >> v;
		Redge.push_back({u,v});
		dsu.add(u,v);
	}
	
	for(auto e : mst)	
	{
		int u = e.S.F, v = e.S.S;
		if(!dsu.ask(u,v)) 
		{
			T[u].push_back(v);
			T[v].push_back(u);
			dsu.add(u,v);
		}
		else Bedge.push_back(e); // Bedge mishe yalaye hazfi
	}
	for(int i = 1; i <= n; i++) scanf("%d", p+i);
	
	
	// comp[Root = 1] = 1
	for(int i = 1; i <= n; i++)
		if(!mark[i]) 
		{
			num++; 
			dfs(i);
		}
	
	dsu.f_reset();
	ll last_ans = 0;
	for(int msk = 0; msk < (1<<k); msk++)
	{
		// in k ta dori nabashano ham bayad check koni
		
		reset();
		bool sw = 0;
		for(int i = 0; i < k; i++)
			if((1<<i) & msk)	
			{	
				int u = comp[Redge[i].F], v = comp[Redge[i].S];
				if(dsu.ask(u,v)) {sw = 1; break;}
				
				dsu.add(u,v);
				Tree[u].push_back(v);
				Tree[v].push_back(u);
			}
		if(sw) continue;	
		
		for(auto e : Bedge)
		{
			int u = comp[e.S.F], v = comp[e.S.S];
			if(!dsu.ask(u,v)) 
			{
				dsu.add(u,v);
				Tree[u].push_back(v);
				Tree[v].push_back(u);
			}
		}
		
		dfs_T(1);
		
		for(auto e : Bedge)
		{	
			int w = e.F; int u = comp[e.S.F], v = comp[e.S.S];
			
			bool seen[num+2];
			memset(seen, 0, sizeof seen);
			while(u != 1)
			{	
				(seen[u] ^= 1);
				u = pa[u];
			}		
			while(v != 1)
			{
				(seen[v] ^= 1);
				v = pa[v];
			}	
			for(int i = 1; i <= num; i++)
				if(seen[i]) W[i] = min(W[i],w);				
		}	
		
		ans = 0;
		for(int i = 0; i < k; i++)
                        if((1<<i) & msk)
                        {
                                int u = comp[Redge[i].F], v = comp[Redge[i].S];
                                if(u == pa[v]) ans += W[v] * stt[v];
				if(v == pa[u]) ans += W[u] * stt[u];
                        }
		last_ans = max(last_ans, ans);
	}
	
	printf("%lld", last_ans);
}
/*
5 5 2
1 5 1
1 2 2
2 3 2
3 4 1
4 5 2
2 4
2 5
1 1 1 1 1
*/

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:92: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:96: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:132:35: 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

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

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 3072 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 3072 KB Output is correct
5 Correct 5 ms 3328 KB Output is correct
6 Correct 5 ms 3328 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 3072 KB Output is correct
5 Correct 5 ms 3328 KB Output is correct
6 Correct 5 ms 3328 KB Output is correct
7 Correct 257 ms 11992 KB Output is correct
8 Correct 264 ms 12136 KB Output is correct
9 Correct 282 ms 11992 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 3072 KB Output is correct
5 Correct 5 ms 3328 KB Output is correct
6 Correct 5 ms 3328 KB Output is correct
7 Correct 257 ms 11992 KB Output is correct
8 Correct 264 ms 12136 KB Output is correct
9 Correct 282 ms 11992 KB Output is correct
10 Correct 2116 ms 12036 KB Output is correct
11 Execution timed out 2582 ms 11992 KB Time limit exceeded
12 Halted 0 ms 0 KB -