oj.uz

답안 #1031627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031627 2024-07-23T02:50:58 Z SamuellH12 Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 124100 KB 
#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define pii pair<int,int>
const int MAXN = 1e5 + 1;
const int SQRT = 50;
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

int block[MAXN], dp[MAXN], order[MAXN], tempo;
vector<int> trafo[MAXN];
vector<pii> best[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int main(){
	ios::sync_with_stdio(false);
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	
	for(int i=0, u, v; i<m; i++)
	{
		scanf("%d %d", &u, &v);
		trafo[v].push_back(u);
		dp[u]++;
	}

	deque<int> fila;
	for(int i=1; i<=n; i++) if(!dp[i]) fila.push_back(i);
	int od = n;
	while(!fila.empty())
	{
		int u = fila.front(); fila.pop_front();
		order[--od] = u;
		shuffle(ALL(trafo[u]), rng);
 
		for(int v : trafo[u])
			if(--dp[v] == 0)
				fila.push_back(v);
	}
	order[n] = -1;

	for(int u : order)
	{
		if(u == -1) break;
        best[u].push_back(pii(0, u));
		for(auto v : trafo[u]){
			for(auto [x, w] : best[v])
				best[u].push_back(pii(x-1, w));
			
			if(best[u].size() >= 300)
			{
				sort(ALL(best[u]));
				best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
			}
		}
 
		sort(ALL(best[u]));
		best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
	}
 
	int t, y;
	while(q--)
	{
		tempo++;
		scanf("%d %d", &t, &y);
 
		for(int i=0, x; i<y; i++)
		{
			scanf("%d", &x);
			block[x] = tempo;
		}
 
		int ans = -1;
 
		for(auto [x, w] : best[t]) 
			if(block[w] != tempo)
			{
				ans = -x;
				break;
			}
 
		if(ans == -1) for(int u : order)
		{
			dp[u] = (block[u] == tempo ? -1 : 0);
	
			for(auto v : trafo[u])
				if(~dp[v]) 
					dp[u] = max(dp[u], dp[v]+1);
	
			if(u == t){ ans = dp[u]; break; }
		}
		
		printf("%d\n", ans);
	}
 
	return 0;	
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d", &t, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5168 KB Output is correct
5 Correct 5 ms 5748 KB Output is correct
6 Correct 5 ms 5724 KB Output is correct
7 Correct 5 ms 5724 KB Output is correct
8 Correct 5 ms 6236 KB Output is correct
9 Correct 5 ms 6236 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 6 ms 6236 KB Output is correct
12 Correct 5 ms 5948 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 5692 KB Output is correct
15 Correct 4 ms 5724 KB Output is correct
16 Correct 4 ms 5724 KB Output is correct
17 Correct 5 ms 5980 KB Output is correct
18 Correct 4 ms 5724 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5168 KB Output is correct
5 Correct 5 ms 5748 KB Output is correct
6 Correct 5 ms 5724 KB Output is correct
7 Correct 5 ms 5724 KB Output is correct
8 Correct 5 ms 6236 KB Output is correct
9 Correct 5 ms 6236 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 6 ms 6236 KB Output is correct
12 Correct 5 ms 5948 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 5692 KB Output is correct
15 Correct 4 ms 5724 KB Output is correct
16 Correct 4 ms 5724 KB Output is correct
17 Correct 5 ms 5980 KB Output is correct
18 Correct 4 ms 5724 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct
20 Correct 338 ms 11988 KB Output is correct
21 Correct 305 ms 11860 KB Output is correct
22 Correct 305 ms 11860 KB Output is correct
23 Correct 315 ms 11700 KB Output is correct
24 Correct 375 ms 98496 KB Output is correct
25 Correct 377 ms 98640 KB Output is correct
26 Correct 363 ms 98564 KB Output is correct
27 Correct 291 ms 122600 KB Output is correct
28 Correct 316 ms 122704 KB Output is correct
29 Correct 294 ms 122264 KB Output is correct
30 Correct 311 ms 122468 KB Output is correct
31 Correct 364 ms 117768 KB Output is correct
32 Correct 314 ms 122288 KB Output is correct
33 Correct 273 ms 82136 KB Output is correct
34 Correct 275 ms 76112 KB Output is correct
35 Correct 247 ms 81492 KB Output is correct
36 Correct 280 ms 101204 KB Output is correct
37 Correct 292 ms 95008 KB Output is correct
38 Correct 277 ms 101204 KB Output is correct

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5168 KB Output is correct
5 Correct 5 ms 5748 KB Output is correct
6 Correct 5 ms 5724 KB Output is correct
7 Correct 5 ms 5724 KB Output is correct
8 Correct 5 ms 6236 KB Output is correct
9 Correct 5 ms 6236 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 6 ms 6236 KB Output is correct
12 Correct 5 ms 5948 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 5692 KB Output is correct
15 Correct 4 ms 5724 KB Output is correct
16 Correct 4 ms 5724 KB Output is correct
17 Correct 5 ms 5980 KB Output is correct
18 Correct 4 ms 5724 KB Output is correct
19 Correct 5 ms 5980 KB Output is correct
20 Correct 338 ms 11988 KB Output is correct
21 Correct 305 ms 11860 KB Output is correct
22 Correct 305 ms 11860 KB Output is correct
23 Correct 315 ms 11700 KB Output is correct
24 Correct 375 ms 98496 KB Output is correct
25 Correct 377 ms 98640 KB Output is correct
26 Correct 363 ms 98564 KB Output is correct
27 Correct 291 ms 122600 KB Output is correct
28 Correct 316 ms 122704 KB Output is correct
29 Correct 294 ms 122264 KB Output is correct
30 Correct 311 ms 122468 KB Output is correct
31 Correct 364 ms 117768 KB Output is correct
32 Correct 314 ms 122288 KB Output is correct
33 Correct 273 ms 82136 KB Output is correct
34 Correct 275 ms 76112 KB Output is correct
35 Correct 247 ms 81492 KB Output is correct
36 Correct 280 ms 101204 KB Output is correct
37 Correct 292 ms 95008 KB Output is correct
38 Correct 277 ms 101204 KB Output is correct
39 Correct 413 ms 99432 KB Output is correct
40 Correct 364 ms 98188 KB Output is correct
41 Correct 382 ms 98388 KB Output is correct
42 Correct 396 ms 99220 KB Output is correct
43 Correct 367 ms 98644 KB Output is correct
44 Correct 368 ms 13080 KB Output is correct
45 Correct 345 ms 12368 KB Output is correct
46 Correct 363 ms 12112 KB Output is correct
47 Correct 334 ms 11896 KB Output is correct
48 Correct 333 ms 11860 KB Output is correct
49 Correct 349 ms 123356 KB Output is correct
50 Correct 906 ms 122192 KB Output is correct
51 Correct 353 ms 12880 KB Output is correct
52 Correct 554 ms 11972 KB Output is correct
53 Correct 325 ms 101712 KB Output is correct
54 Correct 395 ms 95964 KB Output is correct
55 Correct 832 ms 100688 KB Output is correct
56 Correct 980 ms 95572 KB Output is correct
57 Correct 343 ms 12916 KB Output is correct
58 Correct 390 ms 12880 KB Output is correct
59 Correct 575 ms 11988 KB Output is correct
60 Correct 620 ms 12280 KB Output is correct
61 Correct 401 ms 122192 KB Output is correct
62 Correct 336 ms 101200 KB Output is correct
63 Correct 401 ms 95008 KB Output is correct
64 Correct 495 ms 122456 KB Output is correct
65 Correct 460 ms 100524 KB Output is correct
66 Correct 566 ms 95248 KB Output is correct
67 Correct 618 ms 122192 KB Output is correct
68 Correct 594 ms 101124 KB Output is correct
69 Correct 647 ms 94012 KB Output is correct
70 Correct 327 ms 122460 KB Output is correct
71 Correct 340 ms 101064 KB Output is correct
72 Correct 349 ms 94800 KB Output is correct
73 Correct 348 ms 122448 KB Output is correct
74 Correct 324 ms 101204 KB Output is correct
75 Correct 372 ms 94800 KB Output is correct
76 Correct 343 ms 124100 KB Output is correct
77 Correct 320 ms 123064 KB Output is correct
78 Correct 326 ms 122792 KB Output is correct
79 Correct 343 ms 13228 KB Output is correct
80 Correct 327 ms 12276 KB Output is correct
81 Correct 318 ms 11748 KB Output is correct
82 Correct 397 ms 124036 KB Output is correct
83 Correct 421 ms 119768 KB Output is correct
84 Correct 341 ms 122704 KB Output is correct
85 Correct 390 ms 118088 KB Output is correct
86 Correct 337 ms 122828 KB Output is correct
87 Correct 396 ms 118960 KB Output is correct
88 Correct 348 ms 13140 KB Output is correct
89 Correct 360 ms 13188 KB Output is correct
90 Correct 334 ms 12112 KB Output is correct
91 Correct 364 ms 12112 KB Output is correct
92 Correct 332 ms 11860 KB Output is correct
93 Correct 330 ms 11688 KB Output is correct
94 Correct 301 ms 83460 KB Output is correct
95 Correct 315 ms 77396 KB Output is correct
96 Correct 278 ms 82256 KB Output is correct
97 Correct 307 ms 77136 KB Output is correct
98 Correct 277 ms 82772 KB Output is correct
99 Correct 293 ms 76884 KB Output is correct
100 Correct 343 ms 13108 KB Output is correct
101 Correct 342 ms 13140 KB Output is correct
102 Correct 302 ms 12096 KB Output is correct
103 Correct 365 ms 12124 KB Output is correct
104 Correct 333 ms 11800 KB Output is correct
105 Correct 323 ms 11860 KB Output is correct
106 Correct 345 ms 102740 KB Output is correct
107 Correct 384 ms 97432 KB Output is correct
108 Correct 311 ms 101968 KB Output is correct
109 Correct 330 ms 94784 KB Output is correct
110 Correct 301 ms 101968 KB Output is correct
111 Correct 326 ms 95824 KB Output is correct
112 Correct 324 ms 13136 KB Output is correct
113 Correct 367 ms 13252 KB Output is correct
114 Correct 353 ms 12116 KB Output is correct
115 Correct 343 ms 12284 KB Output is correct
116 Correct 334 ms 11908 KB Output is correct
117 Correct 328 ms 11712 KB Output is correct
118 Execution timed out 2039 ms 122368 KB Time limit exceeded
119 Halted 0 ms 0 KB -