Submission #132627

#	Time	Username	Problem	Language	Result	Execution time	Memory
132627		sean617	산만한 고양이 (KOI17_cat)	C++98	45 / 100	1047 ms	34936 KiB

cat

#include <iostream>
#include <cstdio>
#include <vector>
#define N 300005
using namespace std;

typedef long long ll;
ll n, m, k, s, cy, 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 (cy) return;
	if (y[p]) {
		cy = p;
		s += p;
		for (i = v2[p]; i != p; i = v2[i]) {
			s += i;
		}
		return;
	}
	y[p] = 1;
	for (i = 0; i < a[p].size(); i++) {
		if (a[p][i] == q) continue;
		v2[p] = a[p][i];
		g(a[p][i], p);
	}
}
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 == m) {
		g(1, 0);
		cout << s;
		return 0;
	}

	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;
	}

    cout << 0;
    return 0;
}

Compilation message (stderr)

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:34: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:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < k1.size(); i++) {
               ~~^~~~~~~~~~~
cat.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cnt[i] == k1.size()) s += i;
        ~~~~~~~^~~~~~~~~~~~
cat.cpp:45: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 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 55