Submission #245242

#	Time	Username	Problem	Language	Result	Execution time	Memory
245242		A02	Tropical Garden (IOI11_garden)	C++14	100 / 100	3090 ms	29516 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
#include <utility>
#include <queue>

using namespace std;

//void fill_iterated (int N, vector<vector<long long> > &iterated){
//
//    for (int i = 1; i < iterated.size(); i++){
//
//        for (int n = 0; n < 2 * N; n++){
//            iterated[i][n] = iterated[i-1][iterated[i-1][n]];
//        }
//
//    }
//
//}

//vector<long long> iterate_function (int N, long long applications, vector<vector<long long> > &iterated){
//
//
//    vector<long long> function_iterate (2 * N, 0);
//
//    for (int i = 0; i < 2 * N; i++){
//        function_iterate[i] = i;
//    }
//
//    for(int i = 0; i < 30; i++){
//
//        if (applications & (1 << i)){
//
//            for (int j = 0; j < 2 * N; j++){
//                function_iterate[j] = iterated[i][function_iterate[j]];
//            }
//
//        }
//
//    }
//
//    return function_iterate;
//}

vector<long long> count_preimage(long long N, long long P, int Q, int G[], vector<long long> &vertex_image, vector<vector<long long> > &pre_image){
//    cout << endl;
//    cout << P << endl;
//
//    for (int i = 0; i < 2 * N; i++){
//        cout << vertex_image[i] << ' ';
//    }
//    cout << endl;

    vector<long long> results (Q, 0);

    vector<long long> visited (2 * N, -1);

    visited[P] = 0;

    bool is_cycle = false;
    long long cycle_length = 0;

    queue<long long> to_visit;

    to_visit.push(P);

    while (!to_visit.empty()){

        long long current = to_visit.front();
        to_visit.pop();
        long long d = visited[current];

        for (long long i = 0; i < pre_image[current].size(); i++){
            if (pre_image[current][i] == P){
                is_cycle = true;
                cycle_length = d + 1;
            } else {
                to_visit.push(pre_image[current][i]);
                visited[pre_image[current][i]] = d + 1;
            }
        }

    }

    //cout << cycle_length << endl;

    for (int i = 0; i < Q; i++){

        int total = 0;
        for (int n = 0; n < N; n++){
            if (is_cycle){
                if (visited[n] != -1 && G[i] >= visited[n] && (G[i] - visited[n]) % cycle_length == 0){
                    total++;
                }
            } else {
                if (visited[n] != -1 && G[i] == visited[n]){
                    total++;
                }
            }
        }
        results[i] = total;

    }


    return results;

}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

  vector<long long> vertex_image (2 * N, -1);
  //N + i is the trail going to vertex i that goes to i along the most beautiful trail

  vector<pair<long long, long long> > best_trail(N, make_pair(M + 1, -1));

    for (int i = 0; i < M; i++){
        long long s = R[i][0];
        long long e = R[i][1];
        if (best_trail[s].first > i){
            best_trail[s].first = i;
            best_trail[s].second = e;
        }
        if (best_trail[e].first > i){
            best_trail[e].first = i;
            best_trail[e].second = s;
        }
    }

    vector<pair<long, long> > second_best_trail(N, make_pair(M + 1, -1));

    for (int i = 0; i < M; i++){

        long long s = R[i][0];
        long long e = R[i][1];

        if (second_best_trail[s].first > i && i > best_trail[s].first){
            second_best_trail[s].first = i;
            second_best_trail[s].second = e;
        }

        if (second_best_trail[e].first > i && i > best_trail[e].first){
            second_best_trail[e].first = i;
            second_best_trail[e].second = s;
        }
    }

    for (int i = 0; i < N; i++){
        //cout << i << ' ' << best_trail[i].first << ' ' << best_trail[i].second << endl;
        //cout << second_best_trail[i].first << ' ' << second_best_trail[i].second << endl;

        if (second_best_trail[i].second == -1){
            second_best_trail[i] = best_trail[i];
        }
    }

    for (int i = 0; i < N; i++){
        long long new_fountain = best_trail[i].second;

        if (best_trail[i].first == best_trail[new_fountain].first){
            vertex_image[i] = new_fountain + N;
        } else {
            vertex_image[i] = new_fountain;
        }

        new_fountain = second_best_trail[i].second;

        if (second_best_trail[i].first == best_trail[new_fountain].first){
            vertex_image[i + N] = new_fountain + N;
        } else {
            vertex_image[i + N] = new_fountain;
        }
    }

    //target is p or p+N

//    for (int i = 0; i < N; i++){
//        cout << i << " : " << vertex_image[i] << ' ' << vertex_image[i + N] << endl;
//    }

//    vector<vector<long long> > iterated (30, vector<long long> (2 * N, 0));
//
//    iterated[0] = vertex_image;
//
//    fill_iterated(N, iterated);
//
//    for (int i = 0; i < 30; i++){
//        cout << endl;
//        for (int j = 0; j < 2 * N; j++){
//            cout << iterated[i][j] << ' ';
//        }
//        cout << endl << endl;
//    }

//    vector<long long> function_iterate = iterate_function(N, 3, iterated);

//    for (int i = 0; i < 2 * N; i++){
//        cout << function_iterate[i] << ' ';
//    }

//    cout << endl;


    vector<vector<long long> > pre_image (2 * N, vector<long long>());

    for (int i = 0; i < 2 * N; i++){
        pre_image[vertex_image[i]].push_back(i);
    }

    vector<long long> R1 = count_preimage(N, P, Q, G, vertex_image, pre_image);
    vector<long long> R2 = count_preimage(N, P + N, Q, G, vertex_image, pre_image);



    for(int i=0; i<Q; i++){

//        vector<long long> function_iterate = iterate_function(N, G[i], iterated);
//        int total = 0;
//        for (int i = 0; i < N; i++){
//            if (function_iterate[i] == P || function_iterate[i] == P + N){
//                total++;
//            }
//        }


        answer(R1[i] + R2[i]);
    }
}

Compilation message (stderr)

garden.cpp: In function 'std::vector<long long int> count_preimage(long long int, long long int, int, int*, std::vector<long long int>&, std::vector<std::vector<long long int> >&)':
garden.cpp:78:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (long long i = 0; i < pre_image[current].size(); i++){
                               ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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