oj.uz

답안 #26731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26731 2017-07-05T10:50:18 Z model_code Party (POI11_imp) C++11
9 / 100
 1303 ms 10132 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Impreza                                          *
 *   Autor:             Bartosz Gorski                                   *
 *   Opis:              Rozwiazanie bledne                               *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;

#define MAX_N 3000

int n, m, a, b, k, deg[MAX_N],deg0[MAX_N];
bool del[MAX_N], gra[MAX_N][MAX_N];
vector<pair<int, int> > par;
vector<int> cli;

int main() {
	assert(scanf("%d%d", &n, &m) == 2);
	for(int i = 0; i < m; ++i) {
		assert(scanf("%d%d", &a, &b) == 2);
		--a; --b;
		gra[a][b] = gra[b][a] = true;
		++deg[a];
		++deg[b];
	}
	for(int i=0;i<n;i++) deg0[i]=deg[i];
	for(int ii=0;ii<1;ii++)
	{
		cli.clear();
		k=0;
		for(int i=0;i<n;i++)
		{
			del[i]=false;
			deg[i]=deg0[i];
		}
		int krok=0;
		for(int i = 0; i < n; ++i) {
			par.clear();	
			for(int j = 0; j < n; ++j)
				if(!del[j] && deg[j] > 0)
					par.push_back(make_pair(-deg[j], j));
			sort(par.begin(), par.end());
			if (k >= n / 3) goto hell;
			if(par.empty() || k >= n / 3)
				break;
			if (krok==0) cli.push_back(par[min(ii,(int)par.size())].second); else cli.push_back(par[0].second);
			krok++;
			++k;
			a = cli.back();
			for(int j = 0; j < n; ++j)
				if(!gra[a][j] && !del[j]) {
					del[j] = true;
					for(int l = 0; l < n; ++l)
						if(gra[j][l])
							--deg[l];
				}
			del[a] = true;	
		}
	}
hell:
	//printf("%d\n", k);
	for(int i = 0; i < k; ++i)
		printf("%d ", cli[i] + 1);
	return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9992 KB Output is correct
2 Correct 0 ms 9992 KB Output is correct
3 Correct 0 ms 9992 KB Output is correct
4 Correct 0 ms 9992 KB Output is correct
5 Correct 0 ms 9992 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 269 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 436 ms 9992 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 613 ms 10132 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 939 ms 10132 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1146 ms 10132 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1303 ms 10132 KB Wypisano za ma³o osób
2 Halted 0 ms 0 KB -