| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 405298 | Andyvanh1 | Tropical Garden (IOI11_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.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()
typedef vt<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
vt<pair<int,int>> adjlist[150004];
vi adj[300008];
int nex[300008][31];
void gennex(){
for(int j = 1; j < 31; j++){
for(int i = 0; i < 300008; i++){
if(nex[i][j-1]==-1){
nex[i][j] = -1;
}else{
nex[i][j] = nex[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;
}
void count_routes(int n, int m, int p, vt<vi> r,int q,vi 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);
}else if(adjlist[j1][0].second == i){
adj[i].pb(n+j1);
}else{
adj[i].pb(j1);
}
continue;
}
if(adjlist[j1].size()==1){
adj[i].pb(j1);
}else if(adjlist[j1][0].second == i){
adj[i].pb(n+j1);
}else{
adj[i].pb(j1);
}
int j2 = adjlist[i][1].second;
if(adjlist[j2].size()==1){
adj[i+n].pb(j2);
}else if(adjlist[j2][0].second == i){
adj[i+n].pb(n+j2);
}else{
adj[i+n].pb(j2);
}
}
for(int i = 0; i < 2*n; i++){
if(adj[i].empty()){
nex[i][0] = -1;
}else{
nex[i][0] = adj[i][0];
}
}
gennex();
for(int i = 0; i < q; i++){
int x = g[i];
int ans = 0;
for(int j = 0; j < n; j++){
if(get(j,x)==p||get(j,x)==p+n){
ans++;
}
}
answer(ans);
}
}