#include #include #include int post1[100001]; int post2[100001]; int base[100001]; int D[100001]; int R[1001][1001]; int skip[100001]; void delay(int milliseconds) { clock_t start_time = clock(); while (clock() < start_time + milliseconds * CLOCKS_PER_SEC / 1000); } int forefather(int R[1001][1001], int seed, int K, int seq, int* ppcount) { int marcel = 0; if (seq % 2 == 0) { for (int i = 0; i < 1001; i++) { if (R[i][seed] == 1&&skip[i]==0) { skip[i] = 1; post1[*ppcount] = i; (*ppcount)++; marcel = 2; } } } else if (seq % 2 == 1) { for (int i = 0; i < 1001; i++) { if (R[i][seed] == 1&&skip[i]==0) { skip[i] = 1; post2[*ppcount] = i; (*ppcount)++; marcel = 2; } } } return marcel; } void processbase(int bcount) { // 정렬 (내림차순) for (int i = 0; i < bcount - 1; i++) { for (int j = 0; j < bcount - 1 - i; j++) { if (base[j] < base[j + 1]) { int temp = base[j]; base[j] = base[j + 1]; base[j + 1] = temp; } } } // 중복 제거 int new_count = 1; for (int i = 1; i < bcount; i++) { if (base[i] != base[new_count - 1]) { base[new_count++] = base[i]; } } bcount = new_count; // 나머지 값 0으로 초기화 (선택적) for (int i = new_count; i < 100001; i++) { base[i] = 0; } } int min(int bcount, int base[100001], int D[]) { int result = 200000; for (int i = 0; i < bcount; i++) { if (D[base[i]] < result && D[base[i]]>0) { result = D[base[i]]; } else if (D[base[i]] == 0 && skip[base[i]] == 0) { result = 0; skip[base[i]] = 1; } } if (result == 200000) { return 0; } return result; } int meet(int R[1001][1001], int bcount, int base[100001], int D[], int i, int K, int *start, int N) { int j = *start; while (R[base[i]][j] != 1) { j++; if (j > N) { return -1; } } //printf("\nj is %d\n", j); int result = 0; for (int c = 0; c < N+1; c++) { if (R[c][j] == 1 && result <= D[c]) { result = D[c]; } } //printf("\nminimal is %d\n", result); if (result <= 0) { R[base[i]][j] = 0; return j; } else { (*start)=j+1; return -1; } } int countt(int R[1001][1001], int seed, int N) { int count = 0; for (int i = 0; i < N+1; i++) { if (R[seed][i] == 1) { count++; } } return count; } int main() { int T, N, K; scanf("%d", &T); for (size_t i = 0; i < T; i++) { memset(post1, 0, sizeof(post1)); memset(post2, 0, sizeof(post2)); memset(base, 0, sizeof(base)); memset(D, 0, sizeof(D)); memset(R, 0, sizeof(R)); memset(skip, 0, sizeof(skip)); N = 0, K = 0; scanf("%d %d", &N, &K); for (size_t c = 0; c < N; c++) { scanf("%d", &D[c + 1]); } int X, Y; for (size_t j = 0; j < K; j++) { scanf("%d %d", &X, &Y); R[X][Y] = 1; } int W; scanf("%d", &W); int seq = 0; int apcount = 0; int* appcount = &apcount; int bpcount = 0; int* bppcount = &bpcount; int timestock = 0; int time; int stop = 0;; forefather(R, W, K, seq, appcount); seq++; int bcount = 0; if (apcount == 0) { printf("%d\n", D[W]); continue; } while (1) { if (seq % 2 == 1 && apcount == 0) { break; } else if (seq % 2 == 0 && bpcount == 0) { break; } if (seq % 2 == 1) {//홀수번 for (int q = 0; q < apcount; q++) { if (forefather(R, post1[q], K, seq, bppcount) == 0) { base[bcount] = post1[q]; bcount++; } post1[q] = 0; } apcount = 0; } else if (seq % 2 == 0) {//짝수번 for (int q = 0; q < bpcount; q++) { if (forefather(R, post2[q], K, seq, appcount) == 0) { base[bcount] = post2[q]; bcount++; } post2[q] = 0; } bpcount = 0; } processbase(bcount); bcount++; while (base[bcount] != 0 && bcount < 100001) { bcount++; } seq++; } //for (int i = 0; i < 10; i++) { // printf("%d, ", base[i]); //} timestock = 0; time; stop = 0; memset(skip, 0, sizeof(skip)); while (1) { if (stop == 1) { break; } /*delay(1000);*/ //printf("the cost of 2 is %d", D[2]); /*puts(""); for (int i = 0; i < 10; i++) { printf("base[%d]: %d ", i, base[i]); } puts("");*/ processbase(bcount); bcount = 0; /*for (int i = 0; i < 10; i++) { printf("base[%d]: %d ", i, base[i]); } puts("");*/ while (base[bcount] != 0&&bcount<100001) { bcount++; } time = min(bcount, base, D); /*printf("\ntime: %d\n", time);*/ timestock += time; //printf(".%d.\n", time); for (int i = 0; i < bcount; i++) { D[base[i]] -= time; /* printf("D[base[%d]](%d): %d)\n", i, base[i], D[base[i]]);*/ } for (int i = 0; i < bcount; i++) { int di = countt(R, base[i], N); int start = 0; int* pstart = &start; for (int qq = 0; qq < di; qq++) { int yes = meet(R, bcount, base, D, i, K, pstart, N); //printf("the cost of 1 is %d\n", D[1]); //printf("yes: %d", yes); if (yes != -1) { base[bcount] = yes; if (yes == W) { stop = 1; } bcount++; } } } } printf("%d\n", timestock + D[W]); //for (int i = 0; i < 10; i++) { // printf("%d, ", base[i]); //} } }

제출 #85666

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: