oj.uz

Submission #132530

# Submission time Handle Problem Language Result Execution time Memory
132530 2019-07-19T06:24:15 Z sean617 None (KOI17_cat) C++
35 / 100
 1052 ms 23864 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];
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 (v2[p]) {
		s += p;
		for (p = q; p != k; p = v2[p]) s += p;
		return;
	}
	v2[p] = q;
	for (i = 0; i < a[p].size(); i++) {
		if (a[p][i] == q) continue;
		f(a[p][i], 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]]++;
			cnt[k2[i]]++;
		}
		for (i = 1; i <= n; i++) {
			if (cnt[i] == k1.size()) s += i;
		}
		cout << s;
		return 0;
	}
	if (n == m) {
		for (i = 1; i <= n; i++) {
			if (a[i].size() == 3) break;
		}
		if (i > n) {
			cout << n * (n + 1) / 2;
		} else {
			k = i;
			g(i, 0);
		}
		cout << s + k;
		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:30: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:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < k1.size(); i++) {
               ~~^~~~~~~~~~~
cat.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cnt[i] == k1.size()) s += i;
        ~~~~~~~^~~~~~~~~~~~
cat.cpp:40: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 7424 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 605 ms 7928 KB Output is correct
6 Correct 679 ms 7928 KB Output is correct
7 Correct 452 ms 7928 KB Output is correct
8 Correct 664 ms 7852 KB Output is correct
9 Correct 518 ms 8184 KB Output is correct
10 Correct 632 ms 7928 KB Output is correct
11 Correct 546 ms 7928 KB Output is correct
12 Correct 537 ms 8056 KB Output is correct
13 Correct 608 ms 7936 KB Output is correct
14 Correct 717 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 9 ms 7416 KB Output is correct
20 Correct 426 ms 8056 KB Output is correct
21 Correct 1052 ms 8056 KB Output is correct
22 Correct 1050 ms 8016 KB Output is correct
23 Correct 212 ms 7800 KB Output is correct
24 Correct 214 ms 7928 KB Output is correct
25 Correct 8 ms 7388 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 17576 KB Output is correct
2 Correct 119 ms 17400 KB Output is correct
3 Correct 118 ms 17348 KB Output is correct
4 Correct 117 ms 17400 KB Output is correct
5 Correct 117 ms 17400 KB Output is correct
6 Correct 121 ms 17400 KB Output is correct
7 Correct 118 ms 17400 KB Output is correct
8 Correct 119 ms 17408 KB Output is correct
9 Correct 118 ms 17400 KB Output is correct
10 Correct 141 ms 20828 KB Output is correct
11 Correct 141 ms 20836 KB Output is correct
12 Correct 163 ms 20836 KB Output is correct
13 Correct 142 ms 20908 KB Output is correct
14 Correct 138 ms 20880 KB Output is correct
15 Correct 156 ms 21072 KB Output is correct
16 Correct 156 ms 21164 KB Output is correct
17 Correct 159 ms 21080 KB Output is correct
18 Correct 158 ms 21240 KB Output is correct
19 Correct 168 ms 21128 KB Output is correct

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 7424 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 605 ms 7928 KB Output is correct
6 Correct 679 ms 7928 KB Output is correct
7 Correct 452 ms 7928 KB Output is correct
8 Correct 664 ms 7852 KB Output is correct
9 Correct 518 ms 8184 KB Output is correct
10 Correct 632 ms 7928 KB Output is correct
11 Correct 546 ms 7928 KB Output is correct
12 Correct 537 ms 8056 KB Output is correct
13 Correct 608 ms 7936 KB Output is correct
14 Correct 717 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 9 ms 7416 KB Output is correct
20 Correct 426 ms 8056 KB Output is correct
21 Correct 1052 ms 8056 KB Output is correct
22 Correct 1050 ms 8016 KB Output is correct
23 Correct 212 ms 7800 KB Output is correct
24 Correct 214 ms 7928 KB Output is correct
25 Correct 8 ms 7388 KB Output is correct
26 Incorrect 247 ms 23864 KB Output isn't correct
27 Halted 0 ms 0 KB -