| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 390136 | AriaH | Tropical Garden (IOI11_garden) | C++11 | 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.
/** I can do this all day **/
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
int Lev[N], mark[N], Md[N];
vector < int > cyc, lev[N], G[N], adj[N], adt[N], mp[N];
inline void add(int v, int u)
{
printf("yal %d -> %d\n", v, u);
adj[v].push_back(u);
adt[u].push_back(v);
}
void dfs(int v, int H = 0)
{
lev[H].push_back(v);
Lev[H] += (v & 1);
for(auto u : adt[v])
{
dfs(u, H + 1);
}
}
void DFS(int v, int root, int H)
{
int cost = H + Md[root];
if(v & 1) mp[cost % SZ(cyc)].push_back(cost);
for(auto u : adt[v])
{
if(mark[u]) continue;
DFS(u, root, H + 1);
}
}
void count_routs(int n, int m, int st, int E[][2], int q, int Q[])
{
for(int i = 0; i < m; i ++)
{
int v = E[i][0], u = E[i][1];
G[v].push_back(u);
G[u].push_back(v);
}
for(int i = 0; i < n; i ++)
{
if(SZ(G[i]) > 1)
{
int u = G[i][1];
if(G[u][0] == i) add(i << 1, u << 1);
else add(i << 1, u << 1 | 1);
}
else
{
int u = G[i][0];
if(G[u][0] == i) add(i << 1, u << 1);
else add(i << 1, u << 1 | 1);
}
int u = G[i][0];
if(G[u][0] == i) add(i << 1 | 1, u << 1);
else add(i << 1 | 1, u << 1 | 1);
}
int node = st << 1 | 1;
while(!mark[node])
{
mark[node] = 1;
node = adj[node][0];
cyc.push_back(node);
}
if(node != st << 1 | 1)
{
dfs(st << 1 | 1);
for(int i = 0; i < q; i ++)
{
if(Q[i] >= N)
{
printf("0\n");
continue;
}
printf("%d\n", Lev[Q[i]]);
}
return;
}
///printf("alive\n");
reverse(all(cyc));
for(int i = 0; i < SZ(cyc); i ++)
{
Md[cyc[i]] = i;
DFS(cyc[i], cyc[i], 0);
}
for(int i = 0; i < q; i ++)
{
int T = Q[i] % SZ(cyc);
int tot = upper_bound(all(mp[T]), Q[i]) - mp[T].begin();
printf("%d\n", tot);
}
}
/*int n, m, st, q, E[N][2], Q[N];
int main()
{
scanf("%d%d%d%d", &n, &m, &st, &q);
for(int i = 0; i < m; i ++)
{
scanf("%d%d", &E[i][0], &E[i][1]);
}
for(int i = 0; i < q; i ++) scanf("%d", &Q[i]);
count_routs(n, m, st, E, q, Q);
return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/