oj.uz

Submission #132613

# Submission time Handle Problem Language Result Execution time Memory
132613 2019-07-19T08:35:48 Z sean617 None (KOI17_cat) C++
35 / 100
 2000 ms 26780 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], v2[N];
bool z, u[N], y[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);
	}
}

void g(ll p, ll q) {
	ll i;
	if (y[p]) {
		s += p;
		for (i = q; i != p; i = v2[i]) s += i;
		return;
	}
	y[p] = 1;
	v2[p] = q;
	for (i = 0; i < a[p].size(); i++) {
		if (a[p][i] == q) continue;
		g(a[p][i], p);
	}
	v2[p] = 0;
}
int main()
{
	ll i, j, t1, t2;
	cin >> n >> m;
	for (i = 1; i <= m; i++) {
		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]]++;
			cnt[k2[i]]++;
		}
		for (i = 1; i <= n; i++) {
			if (cnt[i] == k1.size()) s += i;
		}
		cout << s;
		return 0;
	}
	if (n == m) {
		g(1, 0);
		cout << s;
		return 0;
	}

    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 'void g(ll, ll)':
cat.cpp:31:16: 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:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < k1.size(); i++) {
               ~~^~~~~~~~~~~
cat.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cnt[i] == k1.size()) s += i;
        ~~~~~~~^~~~~~~~~~~~
cat.cpp:42: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 10 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7420 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 600 ms 8060 KB Output is correct
6 Correct 666 ms 7800 KB Output is correct
7 Correct 452 ms 8028 KB Output is correct
8 Correct 672 ms 7928 KB Output is correct
9 Correct 495 ms 8056 KB Output is correct
10 Correct 644 ms 7924 KB Output is correct
11 Correct 529 ms 7992 KB Output is correct
12 Correct 523 ms 7996 KB Output is correct
13 Correct 644 ms 8056 KB Output is correct
14 Correct 731 ms 7928 KB Output is correct
15 Correct 8 ms 7420 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7448 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 431 ms 8056 KB Output is correct
21 Correct 1056 ms 8056 KB Output is correct
22 Correct 1064 ms 7928 KB Output is correct
23 Correct 211 ms 7800 KB Output is correct
24 Correct 224 ms 7928 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 26780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17936 KB Output is correct
2 Correct 119 ms 17756 KB Output is correct
3 Correct 120 ms 17748 KB Output is correct
4 Correct 120 ms 17676 KB Output is correct
5 Correct 119 ms 17588 KB Output is correct
6 Correct 121 ms 17420 KB Output is correct
7 Correct 118 ms 17528 KB Output is correct
8 Correct 119 ms 17564 KB Output is correct
9 Correct 122 ms 17528 KB Output is correct
10 Correct 140 ms 20968 KB Output is correct
11 Correct 140 ms 20964 KB Output is correct
12 Correct 147 ms 20944 KB Output is correct
13 Correct 144 ms 20972 KB Output is correct
14 Correct 140 ms 20928 KB Output is correct
15 Correct 161 ms 21328 KB Output is correct
16 Correct 165 ms 21332 KB Output is correct
17 Correct 162 ms 21240 KB Output is correct
18 Correct 160 ms 21208 KB Output is correct
19 Correct 164 ms 21184 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7420 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 600 ms 8060 KB Output is correct
6 Correct 666 ms 7800 KB Output is correct
7 Correct 452 ms 8028 KB Output is correct
8 Correct 672 ms 7928 KB Output is correct
9 Correct 495 ms 8056 KB Output is correct
10 Correct 644 ms 7924 KB Output is correct
11 Correct 529 ms 7992 KB Output is correct
12 Correct 523 ms 7996 KB Output is correct
13 Correct 644 ms 8056 KB Output is correct
14 Correct 731 ms 7928 KB Output is correct
15 Correct 8 ms 7420 KB Output is correct
16 Correct 8 ms 7416 KB Output is correct
17 Correct 8 ms 7448 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 8 ms 7416 KB Output is correct
20 Correct 431 ms 8056 KB Output is correct
21 Correct 1056 ms 8056 KB Output is correct
22 Correct 1064 ms 7928 KB Output is correct
23 Correct 211 ms 7800 KB Output is correct
24 Correct 224 ms 7928 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Execution timed out 2048 ms 26780 KB Time limit exceeded
27 Halted 0 ms 0 KB -