Submission #121505

#	Time	Username	Problem	Language	Result	Execution time	Memory
121505		baqargam	Tropical Garden (IOI11_garden)	C++14	0 / 100	12 ms	11084 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

int a,k,n,m,q,p,v1[300005],sz,sz1,sz2,st,ch,res;
bool fx[300005];
vector<pair<int,int> >v[150005];
vector<int>rv[300005];

inline void cch(int x,int dis,int st){
    for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
        if(*it==st) {sz=dis+1;return;}
        cch(*it,dis+1,st);
    }
}

inline void dfs(int x,int dis,int st){
    if(k<dis) return;
    if((x&1)==0 && abs(k-dis)%sz==0)
    {
        res+=(1^fx[x]);
        fx[x]=1;
    }
    for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
        if(*it==st) continue;
        dfs(*it,dis+1,st);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int n=N,m=M,p=P,i;
    for(i=0;i<m;i++){///grafi1
        v[R[i][0]].push_back({i,R[i][1]});
        v[R[i][1]].push_back({i,R[i][0]});
    }
    for(i=0;i<n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(i=0;i<n;i++){///grafi2
        if(v[i].size()==1)
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
            if(v[to][0].first==val)
                v1[(i<<1)^1]=(to<<1)^1;
            else
                v1[(i<<1)^1]=(to<<1);

            if(v[to][0].first==val)
                v1[(i<<1)]=(to<<1)^1;
            else
                v1[(i<<1)]=(to<<1);
        }
        else
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[(i<<1)]=(to<<1)^1;
            else
                v1[(i<<1)]=(to<<1);

            to=v[i][1].second;
            val=v[i][1].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[(i<<1)^1]=(to<<1)^1;
            else
                v1[(i<<1)^1]=(to<<1);

        }
    }

    for(i=0;i<2*n;i++){
        rv[v1[i]].push_back(i);
    }

    sz=1000000003;cch(2*p,0,2*p);sz1=sz;
    sz=1000000003;cch(2*p+1,0,2*p+1);sz2=sz;

    for(i=0; i<Q; i++)
    {
        k=G[i];
        for(int j=0;j<2*n;j++)
            fx[j]=0;
        res=0;
        sz=sz1;dfs((1<<p),0,(1<<p));
        sz=sz2;dfs((1<<p)^1,0,(p<<1)^1);
        answer(res);
    }
}

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