Submission #114681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114681	2019-06-02T09:50:55 Z	WhipppedCream	Toll (APIO13_toll)	C++11	Compilation error	0 ms	0 KB

toll

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef long long ll;
const int maxn = 1e5+5;
const int maxk = 25;
struct edge
{
	int u, v, w;
	bool is_hard, in_mst;
	edge(int _u, int _v, int _w)
	{
		u = _u; v = _v; w = _w;
		is_hard = 0;
		in_mst = 0;
	}
	bool operator < (edge other)
	{
		return w< other.w;
	}
};
int n, m, k;
int sizee;
int par[maxn];
int sz[maxn];
int treecomp[maxn];
int treesz[maxn];
vi adj[maxk];
vi weight[maxk];
int dep[maxk];
int up[maxk];
int subsz[maxk];
int b4[maxk];
void setsz(int x)
{
	sizee = x;
} 
void reset()
{
	for(int i = 1; i<= sizee; i++) par[i] = i;
}
int pong(int x)
{
	if(par[x] == x) return x;
	return par[x] = pong(par[x]);
}
void tfs(int u, int par)
{
	subsz[u] = treesz[u];
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i], w = weight[u][i];
		if(v == par) continue;
		up[v] = w;
		dep[v] = dep[u]+1;
		b4[v] = u;
		tfs(v, u);
		subsz[u] += subsz[v];
	}
}
int main()
{
	scanf("%d %d %d", &n, &m, &k);
	vector<edge> norm;
	vector<edge> sp;
	for(int i = 0; i< m; i++)
	{
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		norm.pb(edge(u, v, w));
	}
	for(int i = 0; i< k; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		sp.pb(edge(u, v, 0));
	}
	for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
	setsz(n);
	for(int i = 0; i< m; i++)
	{
		int a = pong(norm[i].u), b = pong(norm[i].v);
		if(a == b) continue;
		par[a] = b; norm[i].in_mst = true;
	}
	reset();
	for(int i = 0; i< k; i++)
	{
		int a = pong(sp[i].u), b = pong(sp[i].v);
		par[a] = b;
	}
	for(int i = 0; i< m; i++)
	{
		int a = pong(norm[i].u), b = pong(norm[i].v);
		if(a == b) continue;
		par[a] = b;
		norm[i].is_hard = true;
	}
	reset();
	vector<edge> soft;
	for(int i = 0; i< m; i++)
	{
		if(norm[i].is_hard)
		{
			int a = pong(norm[i].u), b = pong(norm[i].v);
			par[a] = b; sz[b] += sz[a];
		}
		else if(norm[i].in_mst) soft.pb(norm[i]);
	}
	int comps = 0;
	for(int i = 1; i<= n; i++)
	{
		if(pong(i) == i)
		{
			comps++; treecomp[i] = comps; treesz[comps] = sz[i];
		}
	}
	for(int i = 1; i<= n; i++)
	{
		if(pong(i) != i)
		{
			treecomp[i] = treecomp[pong[i]];
		}
	}
	ll best = 0;
	for(int mask = 0; mask < (1<<k); mask++)
	{
		setsz(k); reset();
		bool is_cycle = false;
		for(int i = 1; i<= comps; i++)
		{
			adj[i].clear(); weight[i].clear();
		}
		for(int i = 0; i< k; i++)
		{
			if((1<<i)&mask)
			{
				int a = pong(treecomp[sp[i].u]), b = pong(treecomp[sp[i].v]);
				if(a == b)
				{
					is_cycle = true;
					break;
				}
				par[a] = b;
				adj[treecomp[sp[i].u]].pb(treecomp[sp[i].v]); weight[treecomp[sp[i].u]].pb(2e9);
				adj[treecomp[sp[i].v]].pb(treecomp[sp[i].u]); weight[treecomp[sp[i].v]].pb(2e9);
			}
		}
		if(is_cycle) continue;
		vector<edges> gas;
		for(int i = 0; i< (int) soft.size(); i++)
		{
			int a = pong(treecomp[soft[i].u]), b = pong(treecomp[soft[i].v]);
			if(a == b) gas.pb(soft[i]);
			else
			{
				par[a] = b;
				adj[treecomp[soft[i].u]].pb(soft[i].v); weight[treecomp[soft[i].u]].pb(0);
				adj[treecomp[soft[i].v]].pb(soft[i].u); weight[treecomp[soft[i].v]].pb(	0);
			}
		}
		dep[treecomp[1]] = 1; tfs(treecomp[1], 0);
		for(int i = 0; i< (int) gas.size(); i++)
		{
			int u = treecomp[gas[i].u], v = treecomp[gas[i].v];
			int w = gas[i].w;
			if(dep[u]< dep[v]) swap(u, v);
			while(dep[u]> dep[v])
			{
				up[u] = min(up[u], w);
				u = b4[u];
			}
			while(u != v)
			{
				up[u] = min(up[u], w);
				up[v] = min(up[v], w);
				u = b4[u], v = b4[v];
			}
		}
		ll here = 0;
		for(int i = 2; i<= comps; i++) here += subsz[i]*up[i];
		best = max(here, best);
	}
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:121:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
    treecomp[i] = treecomp[pong[i]];
                                 ^
toll.cpp:121:34: error: invalid types 'int [100005][int(int)]' for array subscript
    treecomp[i] = treecomp[pong[i]];
                                  ^
toll.cpp:149:10: error: 'edges' was not declared in this scope
   vector<edges> gas;
          ^~~~~
toll.cpp:149:10: note: suggested alternative: 'edge'
   vector<edges> gas;
          ^~~~~
          edge
toll.cpp:149:15: error: template argument 1 is invalid
   vector<edges> gas;
               ^
toll.cpp:149:15: error: template argument 2 is invalid
toll.cpp:2:12: error: request for member 'push_back' in 'gas', which is of non-class type 'int'
 #define pb push_back
            ^
toll.cpp:153:19: note: in expansion of macro 'pb'
    if(a == b) gas.pb(soft[i]);
                   ^~
toll.cpp:162:31: error: request for member 'size' in 'gas', which is of non-class type 'int'
   for(int i = 0; i< (int) gas.size(); i++)
                               ^~~~
toll.cpp:164:26: error: invalid types 'int[int]' for array subscript
    int u = treecomp[gas[i].u], v = treecomp[gas[i].v];
                          ^
toll.cpp:165:17: error: invalid types 'int[int]' for array subscript
    int w = gas[i].w;
                 ^
toll.cpp:166:19: error: 'v' was not declared in this scope
    if(dep[u]< dep[v]) swap(u, v);
                   ^
toll.cpp:167:22: error: 'v' was not declared in this scope
    while(dep[u]> dep[v])
                      ^
toll.cpp:172:15: error: 'v' was not declared in this scope
    while(u != v)
               ^
toll.cpp:64: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:69:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:77:34: 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", &sz[i]);
                             ~~~~~^~~~~~~~~~~~~~