oj.uz

답안 #516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516 2013-02-28T07:58:09 Z tncks0121 파일 삭제 (GA3_delete) C++
120 / 120
 102 ms 118860 KB 
/* Subtask 1 - 5를 해결하는 코드 */

#include <vector>
#include <malloc.h>
#include <algorithm>

using namespace std;

namespace sttic { int N, M, F, K; };
using namespace sttic;

const int N_ = 5005;
const int INF = 987654321;

int Table[3005][10005];
vector< vector<int> > Gph;

struct Intv {
    int l, r, ln, rn;
    Intv(): l(0), r(0), ln(0), rn(0) { }
	Intv(int l, int r): l(l), r(r), ln(0), rn(0) { }
	bool operator< (const Intv &t) const {
		if(l == INF) return false;
		if(t.l == INF) return true;
		return r != t.r ? r < t.r : l > t.l;
	}
} *D;

int file;
void Renumber( int node ){
	int i;
	if(node >= M){ // leaf node
		D[node].l = D[node].r = ++file;
	}else{
        D[node].l = INF;
        D[node].r = -INF;
		for(int i = 0; i < Gph[node].size(); i++){
			int g = Gph[node][i];
			Renumber(g);
            D[node].l = min(D[node].l, D[g].l);
            D[node].r = max(D[node].r, D[g].r);
		}
	}
}

int DeletePlan( int N, int M, int K, int *A, int *B) {
	int i, j, ret = K;

	sttic::N = N; sttic::M = M; sttic::K = K;
	sttic::F = N + M;

	Gph.resize(M);
	for(i = 1; i < M; i++) Gph[ B[i] ].push_back( i );
	for(i = 0; i < N; i++) Gph[ A[i] ].push_back( i + M );

	D = (Intv*) calloc( F, sizeof(Intv) );
	Renumber (0);
	sort(D, D + M);
	while(D[M - 1].l == INF && M > 0) --M;

	vector<int> X;
	X.push_back(0);
	for(i = 0; i < M; i++) X.push_back( D[i].r );

	sort( X.begin(), X.end() );
	X.resize( distance( X.begin(), unique( X.begin(), X.end() ) ) );

	for(i = 0; i < M; i++){
		D[i].ln = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].l - 1) );
		D[i].rn = distance( X.begin(), lower_bound( X.begin(), X.end(), D[i].r ) );
		//printf("%3d : [%3d, %3d] [%3d, %3d]\n", i, D[i].l - 1, D[i].r, D[i].ln, D[i].rn );
	}

	for(i = 0; i < X.size(); i++){
		for(j = 1; j <= K; j++) Table[i][j] = INF;
	}

	for(j = 1; j <= D[0].r; j++) Table[0][j] = j;
	for(i = 0; i < M; i++){
		Intv &d = D[i]; int len = d.r - d.l + 1;
		if(d.l == INF) continue;
		for(j = 1; j <= K && j <= d.r; j++){
			int &t = Table[d.rn][j];
			t = min(t, Table[d.rn - 1][j]);
			if(j >= len) t = min(t, Table[d.ln][j - len] + 1);
		}
		if(i + 1 < M && d.rn != D[i + 1].rn){
			for(j = d.r + 1; j <= D[i + 1].r && j <= K; j++) 
				Table[d.rn][j] = min(Table[d.rn][j], Table[d.rn][j - 1] + 1);
		}
	}
	
	for(i = 0; i <= K; i++){
		int val = Table[D[M - 1].rn][i] + (K - i);
		if(val < ret) ret = val;
	}

	return ret;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 118396 KB Output is correct
2 Correct 0 ms 118396 KB Output is correct
3 Correct 0 ms 118396 KB Output is correct
4 Correct 0 ms 118396 KB Output is correct
5 Correct 0 ms 118396 KB Output is correct
6 Correct 0 ms 118396 KB Output is correct
7 Correct 0 ms 118396 KB Output is correct
8 Correct 0 ms 118396 KB Output is correct
9 Correct 0 ms 118396 KB Output is correct
10 Correct 0 ms 118396 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 118396 KB Output is correct
2 Correct 2 ms 118396 KB Output is correct
3 Correct 2 ms 118396 KB Output is correct
4 Correct 2 ms 118396 KB Output is correct
5 Correct 2 ms 118396 KB Output is correct
6 Correct 0 ms 118396 KB Output is correct
7 Correct 0 ms 118396 KB Output is correct
8 Correct 0 ms 118396 KB Output is correct
9 Correct 0 ms 118396 KB Output is correct
10 Correct 0 ms 118396 KB Output is correct
11 Correct 1 ms 118396 KB Output is correct
12 Correct 4 ms 118396 KB Output is correct
13 Correct 3 ms 118396 KB Output is correct
14 Correct 6 ms 118396 KB Output is correct
15 Correct 3 ms 118396 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 118556 KB Output is correct
2 Correct 23 ms 118696 KB Output is correct
3 Correct 15 ms 118696 KB Output is correct
4 Correct 33 ms 118696 KB Output is correct
5 Correct 19 ms 118692 KB Output is correct
6 Correct 3 ms 118688 KB Output is correct
7 Correct 4 ms 118556 KB Output is correct
8 Correct 4 ms 118696 KB Output is correct
9 Correct 26 ms 118692 KB Output is correct
10 Correct 11 ms 118552 KB Output is correct
11 Correct 55 ms 118716 KB Output is correct
12 Correct 74 ms 118860 KB Output is correct
13 Correct 67 ms 118852 KB Output is correct
14 Correct 102 ms 118856 KB Output is correct
15 Correct 83 ms 118712 KB Output is correct