| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 405887 | Andyvanh1 | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define eb emplace_back
typedef vt<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
vt<pair<int,int>> adjlist[150004];
vi adj[300008];
vi rev[300008];
int nex[300008][31];
void gennex(){
for(int j = 1; j < 31; j++){
for(auto & i : nex){
if(i[j-1]==-1){
i[j] = -1;
}else{
i[j] = nex[i[j-1]][j-1];
}
}
}
}
int get(int i, int jmp){
for(int j = 0; j < 31; j++){
if(jmp&(1<<j)){
i = nex[i][j];
}
}
return i;
}
int a[300008];
int b[300008];
bool visited[300008];
bool oncycle[300008];
int findcyclelength(){
int node = 0;
while(!visited[node]){
visited[node]=true;
node = nex[node][0];
}
int x = nex[node][0];
oncycle[node] = true;
int ans = 1;
while(x!=node){
oncycle[x] = true;
x = nex[x][0];
ans++;
}
return ans;
}
int numdep[300008];
void dfs_dep(int node, int dep,int p, int n){
if(node<n) {
numdep[dep]++;
}
for(auto& e: rev[node]){
if(e!=p) {
dfs_dep(e, dep + 1, p,n);
}
}
}
void count_routes(int n, int m, int p,int r[][2],int q,int g[]){
for(int i = 0; i < m; i++){
adjlist[r[i][0]].pb({i,r[i][1]});
adjlist[r[i][1]].pb({i,r[i][0]});
}
for(int i = 0; i < n; i++){
sort(all(adjlist[i]));
}
for(int i = 0; i < n; i++){
int j1 = adjlist[i][0].second;
if(adjlist[i].size()==1){
if(adjlist[j1].size()==1){
adj[i].pb(j1);
rev[j1].pb(i);
}else if(adjlist[j1][0].second == i){
adj[i].pb(n+j1);
rev[n+j1].pb(i);
}else{
adj[i].pb(j1);
rev[j1].pb(i);
}
continue;
}
if(adjlist[j1].size()==1){
adj[i].pb(j1);
rev[j1].pb(i);
}else if(adjlist[j1][0].second == i){
adj[i].pb(n+j1);
rev[n+j1].pb(i);
}else{
adj[i].pb(j1);
rev[j1].pb(i);
}
int j2 = adjlist[i][1].second;
if(adjlist[j2].size()==1){
adj[i+n].pb(j2);
rev[j2].pb(i+n);
}else if(adjlist[j2][0].second == i){
adj[i+n].pb(n+j2);
rev[n+j2].pb(i+n);
}else{
adj[i+n].pb(j2);
rev[j2].pb(i+n);
}
}
for(int i = 0; i < 2*n; i++){
if(adj[i].empty()){
nex[i][0] = -1;
}else{
nex[i][0] = adj[i][0];
}
}
gennex();
int lth = findcyclelength();
vi ans(q);
for(int i = 0; i < q; i++){
ans[i] = 0;
}
if(!oncycle[p]){
dfs_dep(p,0,p,n);
for(int i = 0; i < q; i++){
if(g[i]<2*n) {
ans[i] += numdep[g[i]];
}
}
}else{
vi anss(2*n);
dfs_dep(p,0,p,n);
for(int i = 0; i < lth; i++){
anss[i] = numdep[i];
}
for(int i = lth; i < 2*n; i++){
anss[i] = anss[i-lth]+numdep[i];
}
for(int i = 0; i < q; i++){
if(f[i]>=2*n){
g[i] = g[i]%lth+(n/lth)*lth;
}
ans[i]+=anss[g[i]];
}
}
p+=n;
for(int i = 0; i < 2*n; i++){
numdep[i] = 0;
}
if(!oncycle[p]){
dfs_dep(p,0,p,n);
for(int i = 0; i < q; i++){
if(g[i]<2*n) {
ans[i] += numdep[g[i]];
}
}
}else{
vi anss(2*n);
dfs_dep(p,0,p,n);
for(int i = 0; i < lth; i++){
anss[i] = numdep[i];
}
for(int i = lth; i < 2*n; i++){
anss[i] = anss[i-lth]+numdep[i];
}
for(int i = 0; i < q; i++){
if(f[i]>=2*n){
g[i] = g[i]%lth+(n/lth)*lth;
}
ans[i]+=anss[g[i]];
}
}
for(int i = 0; i < q; i++){
answer(ans[i]);
}
}