oj.uz

Submission #333166

# Submission time Handle Problem Language Result Execution time Memory
333166 2020-12-04T21:16:02 Z ly20 Mergers (JOI19_mergers) C++17
Compilation error
 0 ms 0 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;

int n, k, qtt[MAXN], g[MAXN], in[2][MAXN];

int par[MAXN], depth[MAXN], need[MAXN], have[MAXN];
set<int> s[MAXN];
set<int> :: iterator it;
int marc[MAXN];
vector<int> graph[MAXN];
map<pair<int, int>, bool> specialEdge;

void Special(int u, int v)
{
	specialEdge[make_pair(u, v)] = true;
	specialEdge[make_pair(v, u)] = true;
}

void dfs(int v, int p)
{
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u != p)	dfs(u, v);
	}
}

int find(int v)
{
	return (v == par[v]) ? v : par[v] = find(par[v]);
}

void join(int a, int b)
{
	a = find(a), b = find(b);
	if(a == b)	return;
	if(depth[a] > depth[b])	swap(a, b);

	par[a] = b;
	have[b] += have[a];

	for(it = s[a].begin(); it != s[a].end(); it++)
		if(s[b].find(*it) == s[b].end()) need[b] += qtt[*it], s[b].insert(*it);

	if(depth[a] == depth[b])	depth[b]++;
}

int main ()
{
	scanf("%d %d", &n, &k);

	for(int i = 0, u, v; i < n - 1; i++)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
		in[0][u]++, in[0][v]++;
	}

	stack <vector <int>, int> q;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &g[i]);	qtt[g[i]]++;
		in[1][i] = in[0][i];
		if(in[0][i] == 1)	q.push(i);
	}

	for(int i = 1; i <= n; i++)
	{
		par[i] = i;
		need[i] = qtt[g[i]];
		have[i] = 1;
		s[i].insert(g[i]);
	}

	while(!q.empty())
	{
		int v = q.top(); q.pop();
        marc[v] = 1;
		for(int i = 0; i < (int) graph[v].size(); i++)
		{
			int u = graph[v][i];
            if(marc[u] == 1) continue;
            in[0][u]--;
			if(have[find(v)] == need[find(v)])	Special(u, v);
			join(v, u);
			if(in[0][u] <= 1)	q.push(u);
		}
	}

	for(int i = 1; i <= n; i++)
		if(in[1][i] == 1)	q.push(i);

	int ans = 0;
	while(!q.empty())
	{
		int v = q.top(); q.pop();

		for(int i = 0; i < (int) graph[v].size(); i++)
		{
			int u = graph[v][i];
			in[1][u]--;

			if(specialEdge[make_pair(u, v)]){	ans++; in[1][u] = 0; continue;	}
			if(in[1][u] == 1)	in[1][u] = 0, q.push(u);
		}
	}

	printf("%d\n", (ans + 1) >> 1);
}

/*

5 4
1 2
2 3
3 4
3 5
1
2
1
3
4

*/

Compilation message

In file included from /usr/include/c++/9/stack:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:89,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/stl_stack.h: In instantiation of 'class std::stack<std::vector<int>, int>':
mergers.cpp:61:28:   required from here
/usr/include/c++/9/bits/stl_stack.h:121:8: error: 'int' is not a class, struct, or union type
  121 |  using _Uses = typename
      |        ^~~~~
/usr/include/c++/9/bits/stl_stack.h:134:47: error: 'int' is not a class, struct, or union type
  134 |       typedef typename _Sequence::value_type  value_type;
      |                                               ^~~~~~~~~~
/usr/include/c++/9/bits/stl_stack.h:135:46: error: 'int' is not a class, struct, or union type
  135 |       typedef typename _Sequence::reference  reference;
      |                                              ^~~~~~~~~
/usr/include/c++/9/bits/stl_stack.h:136:51: error: 'int' is not a class, struct, or union type
  136 |       typedef typename _Sequence::const_reference const_reference;
      |                                                   ^~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_stack.h:137:46: error: 'int' is not a class, struct, or union type
  137 |       typedef typename _Sequence::size_type  size_type;
      |                                              ^~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:66:23: error: 'class std::stack<std::vector<int>, int>' has no member named 'push'
   66 |   if(in[0][i] == 1) q.push(i);
      |                       ^~~~
mergers.cpp:79:13: error: 'class std::stack<std::vector<int>, int>' has no member named 'top'; did you mean 'pop'?
   79 |   int v = q.top(); q.pop();
      |             ^~~
      |             pop
mergers.cpp:88:24: error: 'class std::stack<std::vector<int>, int>' has no member named 'push'
   88 |    if(in[0][u] <= 1) q.push(u);
      |                        ^~~~
mergers.cpp:93:23: error: 'class std::stack<std::vector<int>, int>' has no member named 'push'
   93 |   if(in[1][i] == 1) q.push(i);
      |                       ^~~~
mergers.cpp:98:13: error: 'class std::stack<std::vector<int>, int>' has no member named 'top'; did you mean 'pop'?
   98 |   int v = q.top(); q.pop();
      |             ^~~
      |             pop
mergers.cpp:106:38: error: 'class std::stack<std::vector<int>, int>' has no member named 'push'
  106 |    if(in[1][u] == 1) in[1][u] = 0, q.push(u);
      |                                      ^~~~
In file included from /usr/include/c++/9/stack:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:89,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/stl_stack.h: In instantiation of 'bool std::stack<_Tp, _Sequence>::empty() const [with _Tp = std::vector<int>; _Sequence = int]':
mergers.cpp:77:17:   required from here
/usr/include/c++/9/bits/stl_stack.h:194:18: error: request for member 'empty' in '((const std::stack<std::vector<int>, int>*)this)->std::stack<std::vector<int>, int>::c', which is of non-class type 'const int'
  194 |       { return c.empty(); }
      |                ~~^~~~~
/usr/include/c++/9/bits/stl_stack.h: In instantiation of 'void std::stack<_Tp, _Sequence>::pop() [with _Tp = std::vector<int>; _Sequence = int]':
mergers.cpp:79:26:   required from here
/usr/include/c++/9/bits/stl_stack.h:269:4: error: request for member 'pop_back' in '((std::stack<std::vector<int>, int>*)this)->std::stack<std::vector<int>, int>::c', which is of non-class type 'int'
  269 |  c.pop_back();
      |  ~~^~~~~~~~
mergers.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d", &g[i]); qtt[g[i]]++;
      |   ~~~~~^~~~~~~~~~~~~