Submission #115874

#	Time	Username	Problem	Language	Result	Execution time	Memory
115874		oolimry	Tropical Garden (IOI11_garden)	C++14	49 / 100	110 ms	10984 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int n = N, m = M;
    typedef pair<int,int> ii;
    ii beautiful[N];
    fill(beautiful,beautiful+N,ii(-1,-1));
    for(int i = 0;i < m;i++){
        int a = R[i][0];
        int b = R[i][1];
        if(beautiful[a].first == -1) beautiful[a].first = b;
        else if(beautiful[a].second == -1) beautiful[a].second = b;
        if(beautiful[b].first == -1) beautiful[b].first = a;
        else if(beautiful[b].second == -1) beautiful[b].second = a;
    }
    for(int i = 0;i < n;i++){
        if(beautiful[i].second == -1) beautiful[i].second = beautiful[i].first;
        //cout << beautiful[i].first << " " << beautiful[i].second << "\n";
    }

    int big = 1000000000;

    int dis[2*n];
    int reach[2*n];
    fill(dis,dis+2*n,-1);
    fill(reach,reach+2*n,-1);
    dis[P] = 0;
    dis[P+N] = 0;
    reach[P] = 1;
    reach[P+N] = 2;
    for(int i = 0;i < 2 * n;i++){
        int a = i;
        set<int> vis;
        stack<int> order;

        while(true){
            //cout << a << " ";
            if(dis[a] != -1){
                int c = 1;
                while(!order.empty()){
                    dis[order.top()] = dis[a] + c;
                    reach[order.top()] = reach[a];
                    order.pop();
                    c++;
                }
                break;
            }
            else if(vis.find(a) != vis.end()){
                while(!order.empty()){
                    dis[order.top()] = big + 7;
                    reach[order.top()] = 0;
                    order.pop();
                }
            }
            vis.insert(a);
            order.push(a);

            int b;
            if(a < n){
                b = beautiful[a].first;
            }
            else{
                a -= n;
                b = beautiful[a].second;
            }
            if(beautiful[b].first == a){
                b += n;
            }
            a = b;
        }
        //cout << "\n";
    }

    for(int i = 0;i < 2 * n;i++){
        //cout << dis[i] << " ";
    }

    ii ptowhere;
    ii nptowhere;

    int a = P;
    set<int> vis;
    while(true){
        if(a == P + N){
            ptowhere = ii(2,vis.size());
            break;
        }
        if(vis.find(a) != vis.end()){
            if(a == P){
                ptowhere = ii(1,vis.size());
            }
            else{
                ptowhere = ii(0,-1);
            }
            break;
        }
        vis.insert(a);


        int b;
        if(a < n){
            b = beautiful[a].first;
        }
        else{
            a -= n;
            b = beautiful[a].second;
        }
        if(beautiful[b].first == a){
            b += n;
        }
        a = b;
    }


    a = P+N;
    vis.clear();
    while(true){
        if(a == P){
            nptowhere = ii(1,vis.size());
            break;
        }
        if(vis.find(a) != vis.end()){
            if(a == P + N){
                nptowhere = ii(2,vis.size());
            }
            else{
                nptowhere = ii(0,-1);
            }
            break;
        }
        vis.insert(a);


        int b;
        if(a < n){
            b = beautiful[a].first;
        }
        else{
            a -= n;
            b = beautiful[a].second;
        }
        if(beautiful[b].first == a){
            b += n;
        }
        a = b;
    }
    //cout << ptowhere.first << " " << ptowhere.second << " " << nptowhere.first << " " << nptowhere.second;


    if(ptowhere.first == 2 && nptowhere.first == 1){
        for(int qq = 0;qq < Q;qq++){
            int x = G[qq];
            int ans = 0;

            for(int i = 0;i < n;i++){
                if(x - dis[i] >= 0 && (x - dis[i]) % (ptowhere.second + nptowhere.second) == 0){
                    ans++;
                    continue;
                }
                if(reach[i] == 1){
                    if((x - dis[i] - ptowhere.second) >= 0 && (x - dis[i] - ptowhere.second) % (ptowhere.second + nptowhere.second) == 0){
                        ans++;
                        continue;
                    }
                }
                else if(reach[i] == 2){
                    if((x - dis[i] - nptowhere.second) >= 0 && (x - dis[i] - nptowhere.second) % (ptowhere.second + nptowhere.second) == 0){
                        ans++;
                        continue;
                    }
                }
            }
            answer(ans);
        }
      
    }
    else{
        for(int qq = 0;qq < Q;qq++){
            int x = G[qq];
            int ans = 0;
            for(int i = 0;i < n;i++){


                if(reach[i] == 1){

                    if(dis[i] == x){
                        ans++;
                        continue;
                    }
                    if(ptowhere.first == 1){
                        if(x - dis[i] >= 0 && (x-dis[i]) % ptowhere.second == 0){
                            ans++;
                            continue;
                        }
                    }
                    else if(ptowhere.first == 2){

                        if(nptowhere.first == 0){
                            if(dis[i] + ptowhere.second == x){
                                ans++;
                                continue;
                            }
                        }
                        else if(nptowhere.first == 2){
                            if((x - dis[i] - ptowhere.second) >= 0 && (x - dis[i] - ptowhere.second) % nptowhere.second == 0){
                                ans++;
                                assert(false);
                                continue;
                            }
                        }
                    }
                }
                else if(reach[i] == 2){
                    if(dis[i] == x){
                        ans++;
                        continue;
                    }
                    if(nptowhere.first == 2){
                        if(x - dis[i] >= 0 && (x-dis[i]) % nptowhere.second == 0){
                            ans++;
                            continue;
                        }
                    }
                    else if(nptowhere.first == 1){
                        if(ptowhere.first == 0){
                            if(dis[i] + nptowhere.second == x){
                                ans++;
                                continue;
                            }
                        }
                        else if(ptowhere.first == 2){
                            if((x-dis[i]-nptowhere.second) >= 0 && (x-dis[i]-nptowhere.second) % ptowhere.second == 0){
                                ans++;
                                continue;
                            }
                        }
                    }
                }
            }
            answer(ans);
        }
    }
}

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