Submission #405889

#	Time	Username	Problem	Language	Result	Execution time	Memory
405889		Andyvanh1	Tropical Garden (IOI11_garden)	C++14	0 / 100	148 ms	54468 KiB

garden

#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(g[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(g[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]);
    }
 
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31