제출 #245166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245166		A02	Tropical Garden (IOI11_garden)	C++14	69 / 100	5062 ms	83220 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;
}

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;
    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(total);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void fill_iterated(int, std::vector<std::vector<long long int> >&)':
garden.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < iterated.size(); i++){
                     ~~^~~~~~~~~~~~~~~~~

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