| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1110403 | jerzyk | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 2'007;
int tab[N][N], il[N][N], nxt[N][N];
vector<pair<int, int>> ed[N * N * 10];
map<pair<pair<int, int>, pair<int, int>>, int> num;
pair<pair<int, int>, pair<int, int>> pos[N * N * 10];
int dp[N * N * 20], wch[N * N * 10];
void Cnt(int n)
{
for(int i = 1; i <= n; ++i)
nxt[i][n + 1] = n + 1;
for(int i = 1; i <= n; ++i)
for(int j = n; j >= 1; --j)
{
nxt[i][j] = nxt[i][j + 1];
il[i][j] = il[i][j + 1] + 1;
if(tab[i][j] == 0) nxt[i][j] = j;
else il[i][j] = 0;
}
}
int FU(int i, int j, int x)
{
while(il[i - 1][j] >= x)
--i;
return i;
}
int FD(int i, int j, int x)
{
while(il[i + 1][j] >= x)
++i;
return i;
}
int GenG(int n)
{
int cnt = 0, v;
queue<int> q;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
if((j != 1 && tab[i][j - 1] == 0) || tab[i][j] == 1) continue;
int u = FU(i, j, il[i][j]), d = FD(i, j, il[i][j]);
pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + il[i][j] - 1));
if(num.find(wsp) != num.end()) continue;
++cnt;
num[wsp] = cnt; pos[cnt] = wsp;
q.push(cnt);
ed[0].pb(make_pair(cnt, (d - u + 1) * il[i][j]));
}
//cerr << "XDD\n";
while(q.size() > 0)
{
v = q.front(); q.pop();
//cerr << "Gen: " << v << " " << pos[v].st.st << " " << pos[v].st.nd << " " << pos[v].nd.st << " " << pos[v].nd.nd << "\n";
for(int r = 0; r < 2; ++r)
{
//cerr << r << "\n";
int i1 = pos[v].st.st, i2 = pos[v].nd.st;
int cr = i1 - 1;
int j = pos[v].st.nd;
if(r == 1)
cr = i2 + 1;
j = nxt[cr][j];
while(j <= pos[v].nd.nd && cr != 0 && cr != n + 1)
{
//cerr << "B " << j << "\n";
int dis = min(il[cr][j], pos[v].nd.nd - j + 1);
int u = FU(i1, j, dis), d = FD(i2, j, dis);
pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + dis - 1));
//cerr << "Ne: " << wsp.st.st << " " << wsp.st.nd << " " << wsp.nd.st << " " << wsp.nd.nd << "\n";
int ne;
if(num.find(wsp) != num.end())
ne = num[wsp];
else
{
++cnt; num[wsp] = cnt;
pos[cnt] = wsp;
ne = cnt;
q.push(cnt);
}
//cerr << ne << "\n";
ed[v].pb(make_pair(ne, (i1 - u + d - i2) * dis));
j += il[cr][j]; j = nxt[cr][j];
}
//cerr << "E\n";
}
}
return cnt;
}
void Tsort(int n)
{
int v;
queue<int> q;
for(int i = 0; i <= n; ++i)
for(int j = 0; j < (int)ed[i].size(); ++j)
++wch[ed[i][j].st];
for(int i = 0; i <= n; ++i)
if(wch[i] == 0)
q.push(i);
while(q.size() > 0)
{
v = q.front(); q.pop();
for(int i = 0; i < (int)ed[v].size(); ++i)
{
dp[ed[v][i].st] = max(dp[ed[v][i].st], dp[v] + ed[v][i].nd);
--wch[ed[v][i].st];
if(wch[ed[v][i].st] == 0)
q.push(ed[v][i].st);
}
}
}
int biggest_stadium(int _N, vector<vector<int>> _F)
{
int n = _N, m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
tab[i][j] = _F[i - 1][j - 1];
Cnt(n);
m = GenG(n);
Tsort(m);
int ans = 0;
for(int i = 1; i <= m; ++i)
ans = max(ans, dp[i]);
return ans;
}