| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1146784 | sano | Tropical Garden (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include "garden.h"
#include "gardenlib.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 10000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
vec<vec<pii>> g;
vec<vec<vec<ll>>> dist;
vec<vec<bool>> bol;
/*
void answer(ll x) {
cout << x << '\n';
return;
}*/
ll dfs(ll x, ll pr, ll typ) {
if (g[x].size() == 1) pr = -1;
For(i, g[x].size()) {
if (g[x][i].ss == pr) continue;
if (bol[x][i]) return dist[x][i][typ];
bol[x][i] = 1;
dist[x][i][typ] = dfs(g[x][i].ff, g[x][i].ss, typ) + 1;
return dist[x][i][typ];
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int pq[]) {
g.clear();
dist.clear();
g.resize(n);
dist.resize(n, vec<vec<ll>>(2, vec<ll>(2, (-1) * NEK)));
For(i, m) {
if (g[r[i][0]].size() != 2) {
g[r[i][0]].push_back({ r[i][1], i });
}
if (g[r[i][1]].size() != 2) {
g[r[i][1]].push_back({ r[i][0], i });
}
}
bol.clear();
bol.resize(n, vec<bool>(2, false));
dist[p][0][0] = 0;
dist[p][1][1] = 0;
bol[p][0] = 1;
For(i, n) {
//0->mozes pouzit najdrahsieho
dfs(i, -1, 0);
dfs(i, g[i][0].ss, 0);
}
bol.clear();
bol.resize(n, vec<bool>(2, false));
bol[p][1] = 1;
For(i, n) {
dfs(i, -1, 1);
dfs(i, g[i][0].ss, 1);
if (g[i].size() == 1) {
dist[i][1][0] = dist[i][0][0];
dist[i][1][1] = dist[i][0][1];
}
}
vec<pii> o;
For(i, q) {
o.push_back({ pq[i], i });
}
sort(o.begin(), o.end());
vec<vec<ll>> pp(2);
vec<vec<ll>> poc(2, vec<ll>(3 * n + 5, 0));
For(i, n) {
For(j, 2) {
if (dist[i][0][j] < 0) continue;
pp[j].push_back(dist[i][0][j]);
poc[j][dist[i][0][j]]++;
}
}
sort(pp[0].begin(), pp[0].end());
sort(pp[1].begin(), pp[1].end());
vec<ll> vys(q, 0);
//vyries pripad ze vychadza iba 1 hrana
//zaciatok divneho pripadu
ll sit1 = 0;
ll q1 = -1, q2 = -1;
ll jtyp = 0;
if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
q1 = dist[g[p][0].ff][jtyp][0] + 1;
if (g[p].size() > 1) {
jtyp = 0;
pii dh = g[p][1];
if (g[dh.ff][0].ss == dh.ss) jtyp = 1;
q2 = dist[dh.ff][jtyp][1] + 1;
}
ll som = 0;
vec<ll> zv;
if (q1 > 0) {
som = 0;
zv.clear();
zv.resize(q1 + 10, 0);
For(i, o.size()) {
while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
zv[pp[0][som] % q1]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q1];
}
}
else {
For(i, o.size()) {
if (o[i].ff < poc[0].size()) {
vys[o[i].ss] += poc[0][o[i].ff];
}
}
}
if (q2 > 0) {
For(i, o.size()) {
som = 0;
zv.clear();
zv.resize(q2 + 10, 0);
while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
zv[pp[1][som] % q2]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q2];
}
}
else {
For(i, o.size()) {
if (o[i].ff < poc[1].size()) {
vys[o[i].ss] += poc[1][o[i].ff];
}
}
}
For(i, q) {
answer(vys[i]);
}
return;
}
/*
int main() {
//zacyklil sa
int num = 0;
while (true) {
int n1, m1, p1, r1[1000][2], q1, g1[1000];
cin >> n1 >> m1 >> p1;
//n1 = rand() % 10 + 2;
//m1 = rand() % 10 + n1;
//p1 = rand() % n1;
For(i, n1) {
cin >> r1[i][0] >> r1[i][1];
//r1[i][0] = i;
//r1[i][1] = rand() % n1;
}
/*For(i, m1 - n1) {
while (true) {
r1[i + n1][0] = rand() % n1;
r1[i + n1][1] = rand() % n1;
if (r1[i + n1][0] != r1[i + n1][1]) break;
}
}*/
cin >> q1;
//q1 = 1;
For(i, q1) {
cin >> g1[i];
//g1[i] = rand() % 1000000000;
}
/*cout << n1 << ' ' << m1 << ' ' << p1 << '\n';
For(i, m1) {
cout << r1[i][0] << ' ' << r1[i][1] << '\n';
}
cout << q1 << '\n';
For(i, q1) {
cout << g1[i] << '\n';
}
cout << num << '\n';
if (num == 49) {
int lol = 1;
}*/
count_routes(n1, m1, p1, r1, q1, g1);
num++;
break;
}
return 0;
}*/