제출 #245223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245223		A02	Tropical Garden (IOI11_garden)	C++14	0 / 100	6 ms	512 KiB

garden

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

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<bool> visited (2 * N, false);

    long long current = vertex_image[P];

    long long cycle_length = 0;

    while (!visited[current]){
        cycle_length++;
        visited[current] = true;
        current = vertex_image[current];
    }

    bool is_cycle = false;
    if (visited[P]){
        is_cycle = true;
    }

    //cout << "is a cycle: " << is_cycle << ' ' << cycle_length << endl;

    if (!is_cycle){

        vector<long long> current_pre_image;
        current_pre_image.push_back(P);
        vector<long long> pre_image_size;



        while (current_pre_image.size() != 0){

            long long total = 0;
            for (int a = 0; a < current_pre_image.size(); a++){
                if (current_pre_image[a] < N){
                    total++;
                }
            }
            pre_image_size.push_back(total);

            vector<long long> new_pre_image;

            for (int i = 0; i < current_pre_image.size(); i++){
                for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
                    new_pre_image.push_back(pre_image[current_pre_image[i]][j]);
                }
            }
            current_pre_image = new_pre_image;

        }

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


            if (G[i] >= pre_image_size.size()){
                results[i] = 0;
            } else {
                results[i] = pre_image_size[G[i]];
            }

            //cout << G[i] << "re" << results[i] << endl;
        }

        return results;

    }

    vector<long long> cycle;

    long long current1 = P;
    for (int i = 0; i < cycle_length; i++){
        cycle.push_back(current1);
        current1 = vertex_image[current1];
    }

    vector<long long> pre_image_size (N, 0);

    current = vertex_image[P];
    int current_offset = cycle_length - 1;

    for (int k = 0; k < cycle_length; k++){
        vector<long long> current_pre_image;

        for (int r = 0; r < pre_image[current].size(); r++){

            if (!visited[pre_image[current][r]]){
                current_pre_image.push_back(pre_image[current][r]);
            }

        }

        long long counter = 1;
        while (current_pre_image.size() != 0){

            long long total = 0;
            for (int a = 0; a < current_pre_image.size(); a++){
                if (current_pre_image[a] < N){
                    total++;
                }
            }
            pre_image_size[(current_offset + counter)] += total;

            vector<long long> new_pre_image;

            for (int i = 0; i < current_pre_image.size(); i++){
                for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
                    new_pre_image.push_back(pre_image[current_pre_image[i]][j]);
                }
            }
            current_pre_image = new_pre_image;

        }

        current = vertex_image[current];
        current_offset--;
    }
    vector<vector<long long> > partial_sums (cycle_length, vector<long long> (N / cycle_length + 1, 0));
    for (int i = 0; i < cycle_length; i++){
        //cout << 'r' << i << endl;
        partial_sums[i][0] = pre_image_size[i];
        for (int j = 1; j * cycle_length + i < N; j++){
            partial_sums[i][j] = partial_sums[i][j - 1] + pre_image_size[j * cycle_length + i];



        }

    }

    //cout << 'p' << partial_sums[1][0] << endl;

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

        long long residue = G[i] % cycle_length;
        long long quotient = (G[i] - residue) / cycle_length;

        if (G[i] > N){

            quotient = partial_sums[residue].size() - 1;

        }

        results[i] = partial_sums[residue][quotient];

        long long pre_cycle = cycle_length - residue;
        if (cycle[pre_cycle] < N){
            results[i]++;
        }

        //cout << G[i] << "re" << results[i] << endl;

    }

    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]);
    }
}

컴파일 시 표준 에러 (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:90:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int a = 0; a < current_pre_image.size(); a++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:99:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < current_pre_image.size(); i++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:100:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (G[i] >= pre_image_size.size()){
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int r = 0; r < pre_image[current].size(); r++){
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:152:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int a = 0; a < current_pre_image.size(); a++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:161:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < current_pre_image.size(); i++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:162:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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