oj.uz

Submission #132477

# Submission time Handle Problem Language Result Execution time Memory
132477 2019-07-19T01:54:13 Z sean617 None (KOI17_cat) C++
12 / 100
 1024 ms 23328 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#define N 300005
using namespace std;

typedef long long ll;
ll n, m, k, s, v[N], cnt[N];
bool z, u[N];
vector<ll> a[N], k1, k2;
void f(ll p, ll q) {
	ll i, num;
	if (v[p] == k) {z = 1; return;}
	v[p] = k;
	for (i =0; i < a[p].size(); i++) {
		num = a[p][i];
		if (num == q || num == k) continue;
		f(num, p);
	}
}
int main()
{
	ll i, j, t1, t2;
	cin >> n >> m;
	while (m--) {
		scanf ("%lld %lld", &t1, &t2);
		a[t1].push_back(t2);
		a[t2].push_back(t1);
		if (t1 > t2) swap(t1, t2);
		if (t1 == t2 -1) u[t1] = 1;
		else if (t1 == 1 && t2 == n) u[n] = 1;
		else {
			k1.push_back(t1);
			k2.push_back(t2);
		}
	}

	if (n <= 5000 && m <= 5000) {
		for (k = 1; k <= n; k++) {
			for (j = 1; j <= n; j++) {
				if (v[j] == k || j == k) continue;
				z = 0;
				f(j, 0);
				if (z) break;
			}
			if (j > n) s += k;
		}
		cout << s;
		return 0;
	}
	for (i = 1; i <= n; i++) {
		if (!u[i]) break;
	}
	if (i > n) {
		for (i = 0; i < k1.size(); i++) {
			cnt[k1[i] + 1]++;
			cnt[k2[i]]--;
		}
		for (i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
		for (i = 1; i <= n; i++) {
			if (cnt[i] == 0) s += i;
		}
		cout << s;
	}
    cout << 0;
    return 0;
}

Compilation message

cat.cpp: In function 'void f(ll, ll)':
cat.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i =0; i < a[p].size(); i++) {
             ~~^~~~~~~~~~~~~
cat.cpp: In function 'int main()':
cat.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < k1.size(); i++) {
               ~~^~~~~~~~~~~
cat.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld", &t1, &t2);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 565 ms 8028 KB Output is correct
6 Correct 679 ms 7800 KB Output is correct
7 Correct 449 ms 8056 KB Output is correct
8 Correct 669 ms 7808 KB Output is correct
9 Correct 508 ms 7928 KB Output is correct
10 Correct 650 ms 7800 KB Output is correct
11 Correct 511 ms 7988 KB Output is correct
12 Correct 519 ms 7964 KB Output is correct
13 Correct 607 ms 7888 KB Output is correct
14 Correct 721 ms 7928 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 447 ms 8056 KB Output is correct
21 Correct 1014 ms 8028 KB Output is correct
22 Correct 1024 ms 7928 KB Output is correct
23 Correct 211 ms 7932 KB Output is correct
24 Correct 217 ms 7772 KB Output is correct
25 Correct 10 ms 7416 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 23328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 19580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 565 ms 8028 KB Output is correct
6 Correct 679 ms 7800 KB Output is correct
7 Correct 449 ms 8056 KB Output is correct
8 Correct 669 ms 7808 KB Output is correct
9 Correct 508 ms 7928 KB Output is correct
10 Correct 650 ms 7800 KB Output is correct
11 Correct 511 ms 7988 KB Output is correct
12 Correct 519 ms 7964 KB Output is correct
13 Correct 607 ms 7888 KB Output is correct
14 Correct 721 ms 7928 KB Output is correct
15 Correct 8 ms 7416 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7416 KB Output is correct
18 Correct 8 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 447 ms 8056 KB Output is correct
21 Correct 1014 ms 8028 KB Output is correct
22 Correct 1024 ms 7928 KB Output is correct
23 Correct 211 ms 7932 KB Output is correct
24 Correct 217 ms 7772 KB Output is correct
25 Correct 10 ms 7416 KB Output is correct
26 Incorrect 287 ms 23328 KB Output isn't correct
27 Halted 0 ms 0 KB -