| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 297158 | Kastanda | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Take me to church
I'll worship like a dog at the shrine of your lies
I'll tell you my sins and you can sharpen your knife
Offer me that deathless death
Good God, let me give you my life
*/
#include<bits/stdc++.h>
#include "garden.h"
#define x first
#define y second
using namespace std;
const int N = 150004, MXQ = 2002;
int n, m, q, p, MN[N], Q[MXQ], RS[MXQ];
int F[N * 2], D[N * 2], qu[N * 2];
vector < pair < int , int > > vec[N * 2], Adj[N];
vector < int > ps[N * 2], Adt[N * 2];
map < int , int > MP;
inline void Solve(int dt)
{
int l = 0, r = 0;
memset(D, -1, sizeof(D));
for (int u : Adt[dt])
D[u] = 1, qu[r ++] = u;
while (r - l)
{
int v = qu[l ++];
for (int u : Adt[v])
if (D[u] == -1)
D[u] = D[v] + 1, qu[r ++] = u;
}
if (D[dt] == -1)
{
for (int i = 0; i < n; i ++)
if (D[i << 1] != -1)
MP[D[i << 1]] ++;
return ;
}
for (int i = 0; i < q; i ++)
vec[Q[i] % D[dt]].push_back({Q[i], i});
for (int i = 0; i < D[dt]; i ++)
sort(vec[i].begin(), vec[i].end()), ps[i].resize(vec[i].size());
for (int i = 0; i < n; i ++)
{
if (D[i << 1] == -1)
continue;
int d = D[i << 1], r = d % D[dt];
int lb = lower_bound(vec[r].begin(), vec[r].end(), pair < int , int > {d, -1}) - vec[r].begin();
if (lb < vec[r].size())
ps[r][lb] ++;
}
for (int i = 0; i < D[dt]; i ++)
{
for (int j = 0; j < (int)ps[i].size() - 1; j ++)
ps[i][j + 1] += ps[i][j];
for (int j = 0; j < (int)vec[i].size(); j ++)
RS[vec[i][j].second] += ps[i][j];
vec[i].clear();
ps[i].clear();
}
return ;
}
void count_routes(int _n, int _m, int _p, int _E[N][2], int _q, int _Q[MXQ])
//int main()
{
n = _n; m = _m; p = _p; q = _q;
//cin >> n >> m >> p >> q;
for (int i = 0; i < q; i ++)
Q[i] = _Q[i];
//cin >> Q[i];
memset(MN, 63, sizeof(MN));
for (int i = 0; i < m; i ++)
{
int v = _E[i][0], u = _E[i][1];
//int v, u;
//cin >> v >> u;
Adj[v].push_back({i, u});
Adj[u].push_back({i, v});
MN[v] = min(MN[v], i);
MN[u] = min(MN[u], i);
}
for (int i = 0; i < n; i ++)
{
F[i << 1] = F[i << 1 | 1] = -1;
sort(Adj[i].begin(), Adj[i].end());
if (Adj[i].size() == 0)
continue;
int u = Adj[i][0].y;
if (MN[u] < Adj[i][0].x || Adj[u].size() == 1)
F[i << 1] = u << 1;
else
F[i << 1] = u << 1 | 1;
if (Adj[i].size() == 1)
continue;
u = Adj[i][1].y;
if (MN[u] < Adj[i][1].x || Adj[u].size() == 1)
F[i << 1 | 1] = u << 1;
else
F[i << 1 | 1] = u << 1 | 1;
}
for (int i = 0; i < n + n; i ++)
if (F[i] != -1)
Adt[F[i]].push_back(i);
/*for (int i = 0; i < n + n; i ++)
printf("%d ", F[i]);
printf("\n");*/
Solve(p << 1);
Solve(p << 1 | 1);
for (int i = 0; i < q; i ++)
{
RS[i] += MP[Q[i]];
answer(RS[i]);
//printf("%d ", RS[i]);
}
return ;
//return 0;
}