답안 #45033 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45033	2018-04-11T04:27:00 Z	ikura355	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	612 ms	4388 KB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e3 + 5;
const int maxq = 2e3 + 5;
const int block = 310;
const int inf = maxn+5;
int n,m,q;
vector<int> way[maxn];
int p[maxn], busy[maxn];
bool vis[maxn];
pii rec[maxn][311], temp[311];
int dp[maxn];
void small_init() {
	for(int u=1;u<=n;u++) {
	    for(int i=0;i<block;i++) rec[u][i] = {-inf, 0};
		rec[u][0] = {0, u};
		for(auto v : way[u]) {
            for(int i=0;i<block;i++) temp[i] = {-inf, 0};
			//merge
			int pos,i,j;
			pos = i = j = 0;
			vis[0] = 1;
			while(pos<block && (i<block || j<block)) {
//                printf("\t%d: merge %d and %d : %d or %d\n",pos,u,v,i,j);
				//choose maximum
				if(j>=block || rec[u][i].X > rec[v][j].X+1) {
					if(!vis[rec[u][i].Y]) temp[pos++] = {rec[u][i].X, rec[u][i].Y};
					vis[rec[u][i].Y] = 1;
					++i;
				}
				else {
					if(!vis[rec[v][j].Y]) temp[pos++] = {rec[v][j].X+1, rec[v][j].Y};
					vis[rec[v][j].Y] = 1;
					++j;
				}
			}
			for(int i=0;i<block;i++) vis[rec[u][i].Y] = vis[rec[v][i].Y] = 0;
			for(int i=0;i<block;i++) rec[u][i] = temp[i];
		}
//		printf("dest = %d\n",u);
//		for(int i=0;i<block;i++) printf("\t{%d, %d}\n",rec[u][i].X,rec[u][i].Y);
	}
}
int small_solve(int u) {
    int ans = -1;
    for(int i=0;i<block;i++) {
        if(!busy[rec[u][i].Y]) {
            ans = rec[u][i].X;
            break;
        }
    }
    if(ans<0) return -1;
    return ans;
}
int large_solve(int pos) {
    for(int u=1;u<=pos;u++) {
        if(busy[u]) dp[u] = -inf;
        else dp[u] = 0;
        for(auto v : way[u]) dp[u] = max(dp[u], dp[v]+1);
    }
    if(dp[pos]<0) return -1;
    return dp[pos];
}
int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0;i<m;i++) {
		int u, v; scanf("%d%d",&u,&v);
		way[v].push_back(u);
	}
	small_init();
	while(q--) {
		int u, k; scanf("%d%d",&u,&k);
		for(int i=0;i<k;i++) scanf("%d",&p[i]);
		for(int i=0;i<k;i++) busy[p[i]] = 1;
		if(k < block) printf("%d\n",small_solve(u));
		else printf("%d\n",large_solve(u));
		for(int i=0;i<k;i++) busy[p[i]] = 0;
	}
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, k; scanf("%d%d",&u,&k);
             ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:76:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<k;i++) scanf("%d",&p[i]);
                        ~~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	576 KB	Output is correct
4	Correct	2 ms	576 KB	Output is correct
5	Correct	6 ms	2928 KB	Output is correct
6	Correct	11 ms	3056 KB	Output is correct
7	Correct	10 ms	3056 KB	Output is correct
8	Correct	11 ms	3056 KB	Output is correct
9	Correct	9 ms	3056 KB	Output is correct
10	Correct	9 ms	3056 KB	Output is correct
11	Correct	10 ms	3056 KB	Output is correct
12	Correct	10 ms	3056 KB	Output is correct
13	Correct	11 ms	3056 KB	Output is correct
14	Correct	10 ms	3056 KB	Output is correct
15	Correct	9 ms	3056 KB	Output is correct
16	Correct	10 ms	3064 KB	Output is correct
17	Correct	10 ms	3064 KB	Output is correct
18	Correct	10 ms	3064 KB	Output is correct
19	Correct	11 ms	3064 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	576 KB	Output is correct
4	Correct	2 ms	576 KB	Output is correct
5	Correct	6 ms	2928 KB	Output is correct
6	Correct	11 ms	3056 KB	Output is correct
7	Correct	10 ms	3056 KB	Output is correct
8	Correct	11 ms	3056 KB	Output is correct
9	Correct	9 ms	3056 KB	Output is correct
10	Correct	9 ms	3056 KB	Output is correct
11	Correct	10 ms	3056 KB	Output is correct
12	Correct	10 ms	3056 KB	Output is correct
13	Correct	11 ms	3056 KB	Output is correct
14	Correct	10 ms	3056 KB	Output is correct
15	Correct	9 ms	3056 KB	Output is correct
16	Correct	10 ms	3064 KB	Output is correct
17	Correct	10 ms	3064 KB	Output is correct
18	Correct	10 ms	3064 KB	Output is correct
19	Correct	11 ms	3064 KB	Output is correct
20	Correct	597 ms	4312 KB	Output is correct
21	Correct	519 ms	4344 KB	Output is correct
22	Correct	612 ms	4388 KB	Output is correct
23	Correct	593 ms	4388 KB	Output is correct
24	Runtime error	3 ms	4388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Subtask #3
0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	576 KB	Output is correct
4	Correct	2 ms	576 KB	Output is correct
5	Correct	6 ms	2928 KB	Output is correct
6	Correct	11 ms	3056 KB	Output is correct
7	Correct	10 ms	3056 KB	Output is correct
8	Correct	11 ms	3056 KB	Output is correct
9	Correct	9 ms	3056 KB	Output is correct
10	Correct	9 ms	3056 KB	Output is correct
11	Correct	10 ms	3056 KB	Output is correct
12	Correct	10 ms	3056 KB	Output is correct
13	Correct	11 ms	3056 KB	Output is correct
14	Correct	10 ms	3056 KB	Output is correct
15	Correct	9 ms	3056 KB	Output is correct
16	Correct	10 ms	3064 KB	Output is correct
17	Correct	10 ms	3064 KB	Output is correct
18	Correct	10 ms	3064 KB	Output is correct
19	Correct	11 ms	3064 KB	Output is correct
20	Correct	597 ms	4312 KB	Output is correct
21	Correct	519 ms	4344 KB	Output is correct
22	Correct	612 ms	4388 KB	Output is correct
23	Correct	593 ms	4388 KB	Output is correct
24	Runtime error	3 ms	4388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

답안 #45033

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 7.0

Subtask #3 0 / 86.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 7.0

Subtask #3
0 / 86.0