oj.uz

Submission #1029801

# Submission time Handle Problem Language Result Execution time Memory
1029801 2024-07-21T10:42:45 Z mindiyak Vision Program (IOI19_vision) C++14
33 / 100
 241 ms 393184 KB 
#include "vision.h"
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
// #include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;

vector<vector<int>> asked(10005,vector<int>(10005,0));
vi check;
int K,H,W;

int convert(pi a){return (W*a.F)+a.S;}

void dfs(pi start){
	priority_queue<pair<int,pi>> arr;

	vector<int> visited(10005,0);
	arr.push({0,start});

	int i = convert(start);
	while(!arr.empty()){
		int dist = -arr.top().F;
		pi node = arr.top().S;
		int j = convert(node);
		arr.pop();
		if(visited[j])continue;
		visited[j] = 1;
		if(dist == K){
			// cout << start.F << "," << start.S << " | " << node.F << "," << node.S << " " << dist << endl;
			if(!asked[i][j]){
				asked[i][j] = 1;
				asked[j][i] = 1;
				vi q = {i,j};
				int a = add_and(q);
				// cout << a << endl;
				check.pb(a);
			}
		}else if(dist < K){
			if(node.F < H-1){
				node.F++;
				arr.push({-dist-1,node});
				node.F--;
			}
			if(node.F >= 1){
				node.F--;
				arr.push({-dist-1,node});
				node.F++;
			}
			if(node.S >= 1){
				node.S--;
				arr.push({-dist-1,node});
				node.S++;
			}
			if(node.S < W-1){
				node.S++;
				arr.push({-dist-1,node});
				node.S--;
			}
		}
	}

	visited.clear();
}

void construct_network(int H_, int W_, int K_) {
	H = H_;W = W_;K = K_;

	FOR(i,0,H){
		FOR(j,0,W){
			dfs({i,j});
		}
	}
	// dfs({0,0});
	add_or(check);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 392432 KB Output is correct
2 Correct 184 ms 392532 KB Output is correct
3 Correct 165 ms 392528 KB Output is correct
4 Correct 166 ms 392416 KB Output is correct
5 Correct 164 ms 392528 KB Output is correct
6 Correct 180 ms 392500 KB Output is correct
7 Correct 165 ms 392528 KB Output is correct
8 Correct 163 ms 392604 KB Output is correct
9 Correct 169 ms 392440 KB Output is correct
10 Correct 176 ms 392528 KB Output is correct
11 Correct 164 ms 392532 KB Output is correct
12 Correct 185 ms 392524 KB Output is correct
13 Correct 170 ms 392440 KB Output is correct
14 Correct 157 ms 392536 KB Output is correct
15 Correct 168 ms 392536 KB Output is correct
16 Correct 166 ms 392532 KB Output is correct
17 Correct 180 ms 392528 KB Output is correct
18 Correct 170 ms 392604 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 392432 KB Output is correct
2 Correct 184 ms 392532 KB Output is correct
3 Correct 165 ms 392528 KB Output is correct
4 Correct 166 ms 392416 KB Output is correct
5 Correct 164 ms 392528 KB Output is correct
6 Correct 180 ms 392500 KB Output is correct
7 Correct 165 ms 392528 KB Output is correct
8 Correct 163 ms 392604 KB Output is correct
9 Correct 169 ms 392440 KB Output is correct
10 Correct 176 ms 392528 KB Output is correct
11 Correct 164 ms 392532 KB Output is correct
12 Correct 185 ms 392524 KB Output is correct
13 Correct 170 ms 392440 KB Output is correct
14 Correct 157 ms 392536 KB Output is correct
15 Correct 168 ms 392536 KB Output is correct
16 Correct 166 ms 392532 KB Output is correct
17 Correct 180 ms 392528 KB Output is correct
18 Correct 170 ms 392604 KB Output is correct
19 Correct 200 ms 392528 KB Output is correct
20 Correct 166 ms 392620 KB Output is correct
21 Correct 169 ms 392540 KB Output is correct
22 Correct 183 ms 392440 KB Output is correct
23 Correct 163 ms 392528 KB Output is correct
24 Correct 165 ms 392532 KB Output is correct
25 Correct 166 ms 392528 KB Output is correct
26 Correct 167 ms 392608 KB Output is correct
27 Correct 169 ms 392520 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 392432 KB Output is correct
2 Correct 184 ms 392532 KB Output is correct
3 Correct 165 ms 392528 KB Output is correct
4 Correct 166 ms 392416 KB Output is correct
5 Correct 164 ms 392528 KB Output is correct
6 Correct 180 ms 392500 KB Output is correct
7 Correct 165 ms 392528 KB Output is correct
8 Correct 163 ms 392604 KB Output is correct
9 Correct 169 ms 392440 KB Output is correct
10 Correct 176 ms 392528 KB Output is correct
11 Correct 164 ms 392532 KB Output is correct
12 Correct 185 ms 392524 KB Output is correct
13 Correct 170 ms 392440 KB Output is correct
14 Correct 157 ms 392536 KB Output is correct
15 Correct 168 ms 392536 KB Output is correct
16 Correct 166 ms 392532 KB Output is correct
17 Correct 180 ms 392528 KB Output is correct
18 Correct 170 ms 392604 KB Output is correct
19 Correct 200 ms 392528 KB Output is correct
20 Correct 166 ms 392620 KB Output is correct
21 Correct 169 ms 392540 KB Output is correct
22 Correct 183 ms 392440 KB Output is correct
23 Correct 163 ms 392528 KB Output is correct
24 Correct 165 ms 392532 KB Output is correct
25 Correct 166 ms 392528 KB Output is correct
26 Correct 167 ms 392608 KB Output is correct
27 Correct 169 ms 392520 KB Output is correct
28 Incorrect 204 ms 393184 KB WA in grader: Too many instructions
29 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 392432 KB Output is correct
2 Correct 184 ms 392532 KB Output is correct
3 Correct 165 ms 392528 KB Output is correct
4 Correct 166 ms 392416 KB Output is correct
5 Correct 164 ms 392528 KB Output is correct
6 Correct 180 ms 392500 KB Output is correct
7 Correct 165 ms 392528 KB Output is correct
8 Correct 163 ms 392604 KB Output is correct
9 Correct 169 ms 392440 KB Output is correct
10 Correct 176 ms 392528 KB Output is correct
11 Correct 164 ms 392532 KB Output is correct
12 Correct 185 ms 392524 KB Output is correct
13 Correct 170 ms 392440 KB Output is correct
14 Correct 157 ms 392536 KB Output is correct
15 Correct 168 ms 392536 KB Output is correct
16 Correct 166 ms 392532 KB Output is correct
17 Correct 180 ms 392528 KB Output is correct
18 Correct 170 ms 392604 KB Output is correct
19 Correct 200 ms 392528 KB Output is correct
20 Correct 166 ms 392620 KB Output is correct
21 Correct 169 ms 392540 KB Output is correct
22 Correct 183 ms 392440 KB Output is correct
23 Correct 163 ms 392528 KB Output is correct
24 Correct 165 ms 392532 KB Output is correct
25 Correct 166 ms 392528 KB Output is correct
26 Correct 167 ms 392608 KB Output is correct
27 Correct 169 ms 392520 KB Output is correct
28 Incorrect 204 ms 393184 KB WA in grader: Too many instructions
29 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 392612 KB Output is correct
2 Correct 156 ms 392472 KB Output is correct
3 Correct 173 ms 392528 KB Output is correct
4 Correct 174 ms 392512 KB Output is correct
5 Correct 171 ms 392456 KB Output is correct
6 Correct 173 ms 392744 KB Output is correct
7 Correct 165 ms 392584 KB Output is correct
8 Correct 167 ms 392576 KB Output is correct
9 Correct 173 ms 392476 KB Output is correct
10 Correct 169 ms 392532 KB Output is correct
11 Correct 165 ms 392528 KB Output is correct
12 Correct 172 ms 392412 KB Output is correct
13 Correct 166 ms 392528 KB Output is correct
14 Correct 163 ms 392408 KB Output is correct
15 Correct 163 ms 392528 KB Output is correct
16 Correct 175 ms 392652 KB Output is correct
17 Correct 172 ms 392488 KB Output is correct
18 Correct 168 ms 392552 KB Output is correct
19 Correct 165 ms 392544 KB Output is correct
20 Correct 170 ms 392528 KB Output is correct
21 Correct 200 ms 392560 KB Output is correct
22 Correct 165 ms 392532 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 392528 KB Output is correct
2 Correct 169 ms 392528 KB Output is correct
3 Correct 173 ms 392912 KB Output is correct
4 Incorrect 241 ms 393164 KB WA in grader: Too many instructions
5 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 393164 KB WA in grader: Too many instructions
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 392432 KB Output is correct
2 Correct 184 ms 392532 KB Output is correct
3 Correct 165 ms 392528 KB Output is correct
4 Correct 166 ms 392416 KB Output is correct
5 Correct 164 ms 392528 KB Output is correct
6 Correct 180 ms 392500 KB Output is correct
7 Correct 165 ms 392528 KB Output is correct
8 Correct 163 ms 392604 KB Output is correct
9 Correct 169 ms 392440 KB Output is correct
10 Correct 176 ms 392528 KB Output is correct
11 Correct 164 ms 392532 KB Output is correct
12 Correct 185 ms 392524 KB Output is correct
13 Correct 170 ms 392440 KB Output is correct
14 Correct 157 ms 392536 KB Output is correct
15 Correct 168 ms 392536 KB Output is correct
16 Correct 166 ms 392532 KB Output is correct
17 Correct 180 ms 392528 KB Output is correct
18 Correct 170 ms 392604 KB Output is correct
19 Correct 200 ms 392528 KB Output is correct
20 Correct 166 ms 392620 KB Output is correct
21 Correct 169 ms 392540 KB Output is correct
22 Correct 183 ms 392440 KB Output is correct
23 Correct 163 ms 392528 KB Output is correct
24 Correct 165 ms 392532 KB Output is correct
25 Correct 166 ms 392528 KB Output is correct
26 Correct 167 ms 392608 KB Output is correct
27 Correct 169 ms 392520 KB Output is correct
28 Incorrect 204 ms 393184 KB WA in grader: Too many instructions
29 Halted 0 ms 0 KB -