Submission #204953

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
204953	2020-02-27T15:02:34 Z	luciocf	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	737 ms	79332 KB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;

int pai[maxn], peso[maxn];

bool mark[maxn];

vector<int> grafo[maxn], comp[maxn];

void Init(void)
{
	for (int i = 1; i <= n; i++)
		pai[i] = i, peso[i] = 1; 
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

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

	Init();

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		char c;

		scanf("%d %d %c", &u, &v, &c);

		if (c == 'T')
			Join(u, v);
		else
		{
			grafo[u].push_back(v);
			grafo[v].push_back(u);
		}
	}

	for (int i = 1; i <= n; i++)
		comp[Find(i)].push_back(i);

	int cc = 0;
	for (int i = 1; i <= n; i++)
		if (Find(i) == i)
			cc++;

	int ans = 0;

	for (int i = 1; i <= n; i++)
	{
		if (Find(i) != i) continue;

		set<int> st;

		for (auto u: comp[i])
			for (auto v: grafo[u])
				if (Find(v) != i)
					st.insert(Find(v));

		if (st.size() == cc-1)
			ans += comp[i].size();
	}
		
	printf("%d\n", ans);
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (st.size() == cc-1)
       ~~~~~~~~~~^~~~~~~
menesinis_bilietas.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
menesinis_bilietas.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %c", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	35436 KB	Output is correct
2	Correct	20 ms	23800 KB	Output is correct
3	Correct	20 ms	23800 KB	Output is correct
4	Correct	52 ms	42232 KB	Output is correct
5	Correct	22 ms	24312 KB	Output is correct
6	Correct	85 ms	26232 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	42232 KB	Output is correct
2	Correct	20 ms	23800 KB	Output is correct
3	Correct	20 ms	23800 KB	Output is correct
4	Correct	24 ms	24044 KB	Output is correct
5	Correct	22 ms	24312 KB	Output is correct
6	Correct	298 ms	35936 KB	Output is correct
7	Correct	737 ms	79332 KB	Output is correct
8	Correct	35 ms	25848 KB	Output is correct
9	Correct	40 ms	26104 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	20 ms	23800 KB	Output is correct
3	Correct	21 ms	23928 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24060 KB	Output is correct
6	Correct	23 ms	23928 KB	Output is correct
7	Correct	21 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	25 ms	24056 KB	Output is correct
10	Correct	20 ms	23800 KB	Output is correct
11	Correct	22 ms	24056 KB	Output is correct
12	Correct	20 ms	23800 KB	Output is correct
13	Correct	21 ms	23800 KB	Output is correct
14	Correct	21 ms	23928 KB	Output is correct
15	Correct	23 ms	23932 KB	Output is correct
16	Correct	20 ms	23800 KB	Output is correct
17	Correct	20 ms	23800 KB	Output is correct
18	Correct	20 ms	23800 KB	Output is correct
19	Correct	20 ms	23800 KB	Output is correct
20	Correct	24 ms	24044 KB	Output is correct

Subtask #4
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	20 ms	23800 KB	Output is correct
3	Correct	21 ms	23928 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24060 KB	Output is correct
6	Correct	23 ms	23928 KB	Output is correct
7	Correct	21 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	25 ms	24056 KB	Output is correct
10	Correct	20 ms	23800 KB	Output is correct
11	Correct	22 ms	24056 KB	Output is correct
12	Correct	20 ms	23800 KB	Output is correct
13	Correct	21 ms	23800 KB	Output is correct
14	Correct	21 ms	23928 KB	Output is correct
15	Correct	23 ms	23932 KB	Output is correct
16	Correct	32 ms	24568 KB	Output is correct
17	Correct	205 ms	33268 KB	Output is correct
18	Correct	83 ms	27256 KB	Output is correct
19	Correct	126 ms	28280 KB	Output is correct
20	Correct	73 ms	26748 KB	Output is correct
21	Correct	129 ms	28280 KB	Output is correct
22	Correct	20 ms	23800 KB	Output is correct
23	Correct	20 ms	23800 KB	Output is correct
24	Correct	20 ms	23800 KB	Output is correct
25	Correct	20 ms	23800 KB	Output is correct
26	Correct	24 ms	24044 KB	Output is correct
27	Correct	22 ms	24312 KB	Output is correct
28	Correct	35 ms	25848 KB	Output is correct
29	Correct	40 ms	26104 KB	Output is correct
30	Correct	85 ms	26232 KB	Output is correct

Subtask #5
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	20 ms	23800 KB	Output is correct
3	Correct	21 ms	23928 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24060 KB	Output is correct
6	Correct	23 ms	23928 KB	Output is correct
7	Correct	21 ms	23800 KB	Output is correct
8	Correct	20 ms	23800 KB	Output is correct
9	Correct	25 ms	24056 KB	Output is correct
10	Correct	20 ms	23800 KB	Output is correct
11	Correct	22 ms	24056 KB	Output is correct
12	Correct	20 ms	23800 KB	Output is correct
13	Correct	21 ms	23800 KB	Output is correct
14	Correct	21 ms	23928 KB	Output is correct
15	Correct	23 ms	23932 KB	Output is correct
16	Correct	32 ms	24568 KB	Output is correct
17	Correct	205 ms	33268 KB	Output is correct
18	Correct	83 ms	27256 KB	Output is correct
19	Correct	126 ms	28280 KB	Output is correct
20	Correct	73 ms	26748 KB	Output is correct
21	Correct	129 ms	28280 KB	Output is correct
22	Correct	232 ms	35436 KB	Output is correct
23	Correct	20 ms	23800 KB	Output is correct
24	Correct	20 ms	23800 KB	Output is correct
25	Correct	52 ms	42232 KB	Output is correct
26	Correct	20 ms	23800 KB	Output is correct
27	Correct	20 ms	23800 KB	Output is correct
28	Correct	24 ms	24044 KB	Output is correct
29	Correct	22 ms	24312 KB	Output is correct
30	Correct	298 ms	35936 KB	Output is correct
31	Correct	737 ms	79332 KB	Output is correct
32	Correct	57 ms	25848 KB	Output is correct
33	Correct	387 ms	36856 KB	Output is correct
34	Correct	117 ms	29816 KB	Output is correct
35	Correct	35 ms	25848 KB	Output is correct
36	Correct	40 ms	26104 KB	Output is correct
37	Correct	85 ms	26232 KB	Output is correct

Submission #204953

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 6.0 / 6.0

Subtask #3 30.0 / 30.0

Subtask #4 35.0 / 35.0

Subtask #5 19.0 / 19.0

Subtask #1
10.0 / 10.0

Subtask #2
6.0 / 6.0

Subtask #3
30.0 / 30.0

Subtask #4
35.0 / 35.0

Subtask #5
19.0 / 19.0