oj.uz

Submission #935917

# Submission time Handle Problem Language Result Execution time Memory
935917 2024-02-29T18:36:06 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
25 / 100
 304 ms 104796 KB 
#include <bits/stdc++.h>
 
using ll = long long;
 
using namespace std;
 
const int N = 5050;
vector<int> g[N];
int used[N], tmp1[N], tmp2[N];
int clc[N][N];

void dfs(int s, int d) {
	clc[d][s] = 1;
	used[s] = 1;
	for (int i : g[s]) {
		if (!used[i]) {
			dfs(i, d);
		}
	}
}
 
void init(int k, vector<int> r) {
    int n = r.size();
    int ok = 0, last, lev = n, iter = 0;
    for (int i = 0; i < n; i++) {
    	tmp1[i] = -1;
    	tmp2[i] = -1;
    }
    while (ok < n) {
        last = -k;
        for (int i = n - 1; i > n - k; i--) {
            if (!r[i]) {
                last = i - n;
                break;
            }
        }
        vector<int> nw = r;
        for (int i = 0; i < n; i++) {
            if (!r[i]) {
                if (i - last >= k) {
                	if (tmp1[i] != -1) {
                		g[tmp1[i]].push_back(i);
                	}
                	if (tmp2[i] != -1) {
                		g[tmp2[i]].push_back(i);
                	}
                    ok++;
                    for (int j = i - 1; j > i - k; j--) {
                        if (j >= 0) {
                            nw[j]--;
                            tmp1[j] = i;
                        } else {
                            nw[j + n]--;
                            tmp1[j + n] = i;
                        }
                    }
                    for (int j = i + 1; j < i + k; j++) {
                        if (j < n) {
                            tmp2[j] = i;
                        } else {
                            tmp2[j - n] = i;
                        }
                    }
                    nw[i] = INT32_MAX / 2;
                }
                last = i;
            }
        }
        swap(nw, r);
        iter++;
        // assert(iter < n + 10);
    }
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < n; j++) {
    		used[j] = 0;
    	}
    	dfs(i, i);
    }
}
 
int compare_plants(int x, int y) {
    if (clc[y][x]) {
        return -1;
    }
    return clc[x][y];
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:24:23: warning: unused variable 'lev' [-Wunused-variable]
   24 |     int ok = 0, last, lev = n, iter = 0;
      |                       ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 37 ms 5332 KB Output is correct
7 Runtime error 30 ms 5968 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 13 ms 21340 KB Output is correct
7 Correct 304 ms 104532 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 13 ms 21336 KB Output is correct
10 Correct 291 ms 104796 KB Output is correct
11 Correct 216 ms 104308 KB Output is correct
12 Correct 217 ms 104528 KB Output is correct
13 Correct 296 ms 104532 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 13 ms 21340 KB Output is correct
7 Correct 304 ms 104532 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 13 ms 21336 KB Output is correct
10 Correct 291 ms 104796 KB Output is correct
11 Correct 216 ms 104308 KB Output is correct
12 Correct 217 ms 104528 KB Output is correct
13 Correct 296 ms 104532 KB Output is correct
14 Runtime error 32 ms 8272 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 61 ms 44440 KB Output is correct
4 Runtime error 49 ms 11604 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 9 ms 7240 KB Output is correct
8 Correct 10 ms 7260 KB Output is correct
9 Correct 10 ms 7512 KB Output is correct
10 Correct 13 ms 7868 KB Output is correct
11 Correct 10 ms 7740 KB Output is correct
12 Correct 13 ms 7516 KB Output is correct
13 Correct 13 ms 7688 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Runtime error 42 ms 10832 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 37 ms 5332 KB Output is correct
7 Runtime error 30 ms 5968 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -