제출 #1057634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057634		SiliconSquared	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	1053 ms	28832 KiB

garden

#include "garden.h"
#include "gardenlib.h"
using namespace std;
#include <vector>
#define INF 999999999
struct node{
    int p=-1;//0
    bool g1=false;//1
    bool g2=false;//1
    bool l1=false;//1
    bool l2=false;//1
    bool f=false;//valid start?
    vector<int> v;//0
    int z1=INF;
    int z2=INF;
    node(){}
};
int e,n;
vector<node> v;
void count_routes(int N, int m, int E, int w[][2], int Q, int G[]){
    n=N;e=E;
    //0 input trails
    v.resize(n*2,node());
    int a,b;
    for (int i=0;i<m;i++){
        a=w[i][0];
        b=w[i][1];
        if (v[b].p==-1){b+=n;}
        if (v[a].p==-1){
            v[a].p=b;
            v[b].v.push_back(a);
            a+=n;
        }else if (v[a+n].p==-1){
            v[a+n].p=b;
            v[b].v.push_back(a+n);
        }
        b%=n;
        if (v[b].p==-1){
            v[b].p=a;
            v[a].v.push_back(b);
        }else if (v[b+n].p==-1){
            v[b+n].p=a;
            v[a].v.push_back(b+n);
        }
    }
    for (int i=0;i<n;i++){
        if (v[i+n].p==-1){
            v[i+n].p=v[i].p;
        }
    }
    //1 find loops
    int ra,rb;
    a=e;
    ra=0;
    while (!v[a].g1){
        v[a].g1=true;
        ra++;
        a=v[a].p;
    }
    if (a!=e){ra=1;}
    a=e+n;
    rb=0;
    while (!v[a].g2){
        v[a].g2=true;
        rb++;
        a=v[a].p;
    }
    if (a!=e+n){rb=1;}
    a=e;//print(e);
    for (int i=0;i<ra;i++){
        // print(a);
        v[a].l1=true;
        a=v[a].p;
    }
    a=e+n;
    for (int i=0;i<rb;i++){
        v[a].l2=true;
        a=v[a].p;
    }
    //2 grow trees
    vector<pair<int,int>> q;
    pair<int,int> p;
    a=e;
    for (int i=0;i<ra;i++){
        q.clear();
        q.push_back({a,(ra-i)%ra});
        while (!q.empty()){
            p=q[q.size()-1];//print(p.first);
            q.pop_back();
            if (v[p.first].l1&&p.second!=((ra-i)%ra)){continue;}
            v[p.first].z1=p.second;
            for (int j:v[p.first].v){
                q.push_back({j,p.second+1});
            }
        }
        a=v[a].p;
    }
    a=e+n;
    for (int i=0;i<rb;i++){
        q.clear();
        q.push_back({a,(rb-i)%rb});
        while (!q.empty()){
            p=q[q.size()-1];
            q.pop_back();
            if (v[p.first].l2&&p.second!=((rb-i)%rb)){continue;}
            v[p.first].z2=p.second;
            for (int j:v[p.first].v){
                q.push_back({j,p.second+1});
            }
        }
        a=v[a].p;
    }
    // for (int i=0;i<n*2;i++){print(v[i].z1);print(v[i].z2);}
    //3 answer queries
    int z;
    for (int i=0;i<Q;i++){
        a=G[i];
        z=0;
        for (int j=0;j<n;j++){
            if (v[j].z1==a){
                z++;
            }else if (ra!=1 && a>=v[j].z1 && ((a-v[j].z1)%ra==0)){
                z++;
            }else if (v[j].z2==a){
                z++;
            }else if (rb!=1 && a>=v[j].z2 && ((a-v[j].z2)%rb==0)){
                z++;
            }
        }
        answer(z);
    }
}

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