# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
405298 | Andyvanh1 | Tropical Garden (IOI11_garden) | C++14 | 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.
#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);
}
}