| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 239929 | 2020-06-17T14:03:29 Z | Borbi | Skandi (COCI20_skandi) | C++14 | 72 ms | 18812 KB |
#include <bits/stdc++.h>
using namespace std;
/*struct edge
{
int next, to, flow;
edge(int _to, int _next, int _flow)
{
next = _next; to = _to; flow = _flow;
}
};*/
const int MAXN = 1e4 + 5;
int n, m;
string str[MAXN];
/*edge e[MAXM];
int head[MAXN], br;
void add_edge(int v, int w, int c)
{
e[br] = edge(w, head[v], c);
head[v] = br++;
}*/
map <int, pair<int, int> > r_a, c_a;
int cntr, cntc;
int rw[MAXN][MAXN], col[MAXN][MAXN];
vector <int> graph[MAXN];
int vis[MAXN];
void read_input()
{
cin >> n >> m;
/*for(int i = 0; i < MAXN; i++)
{
head[i] = -1;
}*/
for(int i = 0; i < n; i++)
{
cin >> str[i];
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(str[i][j] == '1') continue;
if(str[i][j - 1] == '1')
{
rw[i][j] = cntr++;
r_a[cntr - 1] = {i, j};
}
else
{
rw[i][j] = rw[i][j - 1];
}
if(str[i - 1][j] == '1')
{
col[i][j] = cntc++;
c_a[cntc - 1] = {i, j};
}
else
{
col[i][j] = col[i - 1][j];
}
}
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(str[i][j] == '0')
{
//cout << r_a[rw[i][j]].first << " " << r_a[rw[i][j]].second << " " << c_a[col[i][j]].first << " " << c_a[col[i][j]].second << "\n";
graph[rw[i][j]].push_back(cntr + col[i][j]);
graph[cntr + col[i][j]].push_back(rw[i][j]);
}
}
}
//cout << cntr << " " << cntc << "\n";
}
bool matched[MAXN];
int con[MAXN];
int timer;
bool match(int v)
{
if(vis[v] == timer) return false;
vis[v] = timer;
for(auto x : graph[v])
{
if(con[x] == -1 || match(con[x]))
{
con[x] = v;
return matched[v] = true;
}
}
return false;
}
bool added[MAXN];
//vector <int> z;
void dfs(int v, bool t)
{
if(!added[v])
{
//z.push_back(v);
added[v] = true;
}
else return;
if(t)
{
cout << "DAS";
}
for(auto x : graph[v])
{
if(t == 0)
{
if(con[x] == -1)
{
dfs(x, t ^ 1);
}
}
else
{
if(matched[x])
{
dfs(x, t ^ 1);
}
}
}
}
void solve()
{
for(int i = 0; i < MAXN; i++)
{
con[i] = -1;
}
for(int i = 0; i < cntr; i++)
{
timer++;
match(i);
//cout << matched[i];
}
for(int i = 0; i < cntr; i++)
{
if(!matched[i])
{
dfs(i, 0);
}
}
vector <int> fst, scnd;
for(int i = 0; i < cntr; i++)
{
if(!added[i])
{
fst.push_back(i);
}
}
for(int i = 0; i < cntc; i++)
{
if(added[i + cntr])
{
scnd.push_back(i);
}
}
cout << fst.size() + scnd.size() << "\n";
for(auto x : fst)
{
cout << r_a[x].first + 1 << " " << r_a[x].second << " DESNO\n";
}
for(auto x : scnd)
{
cout << c_a[x].first << " " << c_a[x].second + 1 << " DOLJE\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
read_input();
solve();
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 1024 KB | Correct. |
| 2 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 3 | Correct | 5 ms | 1024 KB | Correct. |
| 4 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 5 | Correct | 5 ms | 1024 KB | Correct. |
| 6 | Correct | 6 ms | 1024 KB | Correct. |
| 7 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 8 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 9 | Correct | 5 ms | 896 KB | Correct. |
| 10 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 11 | Correct | 5 ms | 1024 KB | Correct. |
| 12 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 13 | Correct | 5 ms | 1024 KB | Correct. |
| 14 | Correct | 5 ms | 1024 KB | Correct. |
| 15 | Correct | 5 ms | 896 KB | Correct. |
| 16 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 17 | Correct | 5 ms | 896 KB | Correct. |
| 18 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 19 | Correct | 6 ms | 1024 KB | Correct. |
| 20 | Correct | 5 ms | 1024 KB | Correct. |
| 21 | Correct | 5 ms | 1024 KB | Correct. |
| 22 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 23 | Correct | 5 ms | 1024 KB | Correct. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 6 ms | 2304 KB | First line is correct, but the reconstruction is not. |
| 2 | Partially correct | 8 ms | 2432 KB | First line is correct, but the reconstruction is not. |
| 3 | Partially correct | 7 ms | 3584 KB | First line is correct, but the reconstruction is not. |
| 4 | Partially correct | 6 ms | 2100 KB | First line is correct, but the reconstruction is not. |
| 5 | Partially correct | 6 ms | 2304 KB | First line is correct, but the reconstruction is not. |
| 6 | Partially correct | 6 ms | 1664 KB | First line is correct, but the reconstruction is not. |
| 7 | Partially correct | 5 ms | 1536 KB | First line is correct, but the reconstruction is not. |
| 8 | Partially correct | 6 ms | 2432 KB | First line is correct, but the reconstruction is not. |
| 9 | Partially correct | 9 ms | 5120 KB | First line is correct, but the reconstruction is not. |
| 10 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 11 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 12 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 13 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 14 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 15 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 16 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 17 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 18 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 19 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 20 | Partially correct | 10 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 21 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 22 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 23 | Partially correct | 8 ms | 5376 KB | First line is correct, but the reconstruction is not. |
| 24 | Partially correct | 11 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 25 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 26 | Partially correct | 10 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 1024 KB | Correct. |
| 2 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 3 | Correct | 5 ms | 1024 KB | Correct. |
| 4 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 5 | Correct | 5 ms | 1024 KB | Correct. |
| 6 | Correct | 6 ms | 1024 KB | Correct. |
| 7 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 8 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 9 | Correct | 5 ms | 896 KB | Correct. |
| 10 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 11 | Correct | 5 ms | 1024 KB | Correct. |
| 12 | Partially correct | 6 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 13 | Correct | 5 ms | 1024 KB | Correct. |
| 14 | Correct | 5 ms | 1024 KB | Correct. |
| 15 | Correct | 5 ms | 896 KB | Correct. |
| 16 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 17 | Correct | 5 ms | 896 KB | Correct. |
| 18 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 19 | Correct | 6 ms | 1024 KB | Correct. |
| 20 | Correct | 5 ms | 1024 KB | Correct. |
| 21 | Correct | 5 ms | 1024 KB | Correct. |
| 22 | Partially correct | 5 ms | 1024 KB | First line is correct, but the reconstruction is not. |
| 23 | Correct | 5 ms | 1024 KB | Correct. |
| 24 | Partially correct | 6 ms | 2304 KB | First line is correct, but the reconstruction is not. |
| 25 | Partially correct | 8 ms | 2432 KB | First line is correct, but the reconstruction is not. |
| 26 | Partially correct | 7 ms | 3584 KB | First line is correct, but the reconstruction is not. |
| 27 | Partially correct | 6 ms | 2100 KB | First line is correct, but the reconstruction is not. |
| 28 | Partially correct | 6 ms | 2304 KB | First line is correct, but the reconstruction is not. |
| 29 | Partially correct | 6 ms | 1664 KB | First line is correct, but the reconstruction is not. |
| 30 | Partially correct | 5 ms | 1536 KB | First line is correct, but the reconstruction is not. |
| 31 | Partially correct | 6 ms | 2432 KB | First line is correct, but the reconstruction is not. |
| 32 | Partially correct | 9 ms | 5120 KB | First line is correct, but the reconstruction is not. |
| 33 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 34 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 35 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 36 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 37 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 38 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 39 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 40 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 41 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 42 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 43 | Partially correct | 10 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 44 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 45 | Partially correct | 8 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 46 | Partially correct | 8 ms | 5376 KB | First line is correct, but the reconstruction is not. |
| 47 | Partially correct | 11 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 48 | Partially correct | 9 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 49 | Partially correct | 10 ms | 5248 KB | First line is correct, but the reconstruction is not. |
| 50 | Runtime error | 72 ms | 18812 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 51 | Halted | 0 ms | 0 KB | - |