Submission #851278

#	Time	Username	Problem	Language	Result	Execution time	Memory
851278		Halym2007	Parachute rings (IOI12_rings)	C++17	55 / 100	4019 ms	101696 KiB

rings

//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define pb push_back
const int MAXM = 1e6 + 5;
#define ff first
#define ss second
vector <int> v[MAXM];
int n, comp, cycle, san[MAXM], tr;
bool rem[MAXM], vis[MAXM], gir, birgezek;
int bol[MAXM], oo;
bool bolonok = 0;
vector <int> ayyr, ko;
void Init(int N) {
	n = N;
}

void dfs (int x, int pr) {
	vis[x] = 1;
	for (int i : v[x]) {
		if (rem[i] or i == pr) continue;
		if (vis[i]) {
			cycle = 1;
			continue;
		}
		dfs (i, x);
	} 
}

void dfs1 (int x, int pr) {
	san[x] = 1;
	comp++;
	for (int i : v[x]) {
		if (i == pr or rem[i]) continue;
		if (san[i]) {
			cycle = 1;
			continue;
		}
		dfs1 (i, x);
	}
}

int CountCritical() {
	if ((int)ko.sz > 1) return 0;
	if (bolonok) return 0;
	int jogap = 0;
	if (!birgezek) {
		for (int i = 0; i < n; ++i) {
			if ((int)v[i].sz > 3) {
				ayyr.clear();
				ayyr.pb (i);
				break;
			}
		}
		if (ayyr.empty()) {
			for (int i = 0; i < n; ++i) {
				if ((int)v[i].sz == 3) {
					ayyr.pb (i);
					for (int j : v[i]) {
						ayyr.pb (j);
					}
					break;
				}
			}
		}
	}
	if (!ayyr.empty()) {
		birgezek = 1;
		for (int i : ayyr) {
			rem[i] = 1;
			cycle = 0;
			for (int j = 0; j < n; ++j) {
				san[j] = (int)v[j].sz;
			}
			for (int j = 0; j < n; ++j) {
				if (rem[j] or vis[j]) continue;
				dfs (j, -1);
			}
			for (int j : v[i]) {
				san[j]--;
			}
			san[i] = 0;
			bool aa = 0;
			if (cycle) aa = 1;
			for (int j = 0; j < n; ++j) {
				if (san[j] > 2) aa = 1;
				san[j] = vis[j] = 0;
			}
			rem[i] = 0;
			if (!aa) {
				jogap++;
			}
		}
		if (!jogap) bolonok = 1;
		return jogap;			
	}
	else {
		int opysy = 0;
		int jogap1 = 0;
		for (int i = 0; i < n; ++i) {
			if (!san[i]) {
				cycle = 0;
				comp = 0;
				dfs1 (i, -1);
				opysy += cycle;
				if (cycle) {
					jogap = comp;
				}	
				else {
					jogap1 += comp;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			san[i] = 0;
		}
		if (opysy > 1) {
			bolonok = 1;
			return 0;
		}
		else if (opysy == 1) return jogap;
		else return jogap1;
	}
	return n;
}

void Link(int a, int b) {
	v[a].pb (b);
	v[b].pb (a);
	if ((int)ko.sz > 1) return;
	if ((int)v[a].sz > 3) {
		if (ko.empty()) ko.pb (a);
		else if (ko[0] != a) ko.pb (a);
	}
	if ((int)ko.sz > 1) return;
	if ((int)v[b].sz > 3) {
		if (ko.empty()) ko.pb (b);
		else if (ko[0] != b) ko.pb (b);
	}
}

 
//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//
//#define inbuf_len 1 << 16
//#define outbuf_len 1 << 16
//
//int main() {
//	freopen("input3.txt", "r", stdin);
//  int tmp;
//
//  /* Set input and output buffering */
//  char *inbuf, *outbuf;
//  inbuf = (char*) malloc(inbuf_len * sizeof(char));
//  outbuf = (char*) malloc(outbuf_len * sizeof(char));
//  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
//  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
//
//  int N, L;
//   tmp = scanf("%d %d", &N, &L);
//  assert(tmp == 2);
//  Init(N);
//
//  int i;
//  for (i = 0; i < L; i++) {
//    int A, B;
//    tmp = scanf("%d", &A);
//    if (A == -1) {
//      int critical;
//      critical = CountCritical();
//      printf("%d\n", critical);
//    } else {
//      tmp = scanf("%d", &B);
//      assert(tmp == 1);
//      Link(A, B);
//    }
//  }
//
//  return 0;
//
//}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31