oj.uz

Submission #333161

# Submission time Handle Problem Language Result Execution time Memory
333161 2020-12-04T21:04:54 Z ly20 Mergers (JOI19_mergers) C++17
0 / 100
 424 ms 80852 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;

vector<int> graph[MAXN];
int marc[MAXN];
map<pair<int, int>, bool> specialEdge;

void Special(int u, int v)
{
    //printf("%d %d s\n", u, 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 pai[MAXN], tam[MAXN];
vector <int> grafo[MAXN];
void une(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return;
    if(tam[a] < tam[b]) swap(a, b);
    pai[b] = a;
    tam[a] += tam[b];
}
int acha(int a) {
    if(a == pai[a]) return a;
    return pai[a] = acha(pai[a]);
}
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]++;
	}

	queue<int> q;
	for(int i = 1; i <= n; i++)
	{
	    pai[i] = i; tam[i] = 1;
		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.front(); 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(in[0][u] >= 0 && have[find(v)] == need[find(v)])	Special(u, v);
			if(in[0][u] >= 0)	join(v, u);
			if(in[0][u] <= 1)	in[0][u] = 0,	q.push(u);
		}
	}

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

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < graph[i].size(); j++) {
            int viz = graph[i][j];
            if(specialEdge[make_pair(i, viz)] == true) continue;
            else une(i, viz);
        }
    }
	int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < graph[i].size(); j++) {
            int viz = graph[i][j];
            //printf("%d %d\n", i, viz);
            if(specialEdge[make_pair(i, viz)]) {
                    grafo[acha(i)].push_back(acha(viz));
                //printf("%d %d\n", i, viz);
            }
        }
    }
    for(int i = 1; i <= n; i++) if(grafo[i].size() == 1) ans++;
	printf("%d\n", (ans + 1) >> 1);
}

/*

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

*/

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j = 0; j < graph[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
mergers.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int j = 0; j < graph[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
mergers.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |   scanf("%d", &g[i]); qtt[g[i]]++;
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Incorrect 30 ms 47340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Incorrect 30 ms 47340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Incorrect 30 ms 47340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 72164 KB Output is correct
2 Incorrect 424 ms 80852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Incorrect 30 ms 47340 KB Output isn't correct
4 Halted 0 ms 0 KB -