oj.uz

답안 #1066746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066746 2024-08-20T06:11:13 Z Cyanberry 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 1 ms 856 KB 
        #include <bits/stdc++.h>
        using namespace std;
        #include "gardenlib.h"
         
        void count_routes(int fountains, int pathCount, int dest, int paths[][2], int groupCount, int groups[]) {
            vector<vector<int>> graf(pathCount, vector<int>{});
            for (int i = 0; i < pathCount; ++i) {
                graf[paths[i][0]].push_back(paths[i][1]);
                graf[paths[i][1]].push_back(paths[i][0]);
            }
            vector<int> lengths(pathCount, 0);
            for (int i = 0; i < pathCount; ++i) {
                if (lengths[i] == 0) {
                    int counting = -1, curr = i, prev = -1, dist;
                    // cout<<'+'<<i<<'\n';
                    while (curr != dest) {
                        lengths[curr] = counting;
                        if (prev != graf[curr][0] || graf[curr].size() == 1) {
                            prev = curr;
                            curr = graf[curr][0];
                        } else {
                            prev = curr;
                            curr = graf[curr][1];
                        }
                        // cout<<counting<<'\n';
                        --counting;
                        if (lengths[curr] > 0) {
                            dist = lengths[curr] - counting + 1;
                            break;
                        }
                        if (lengths[curr] < 0 && lengths[curr] - counting > 2) {
                            dist = -1;
                            break;
                        }
                        if (curr == dest) {
                            dist = -counting;
                            break;
                        }
                        
                    }
                    curr = i, prev = -1;
                    if (dist < 0) continue;
                    while (curr != dest) {
                        if (lengths[curr] < 0) lengths[curr] += dist;
                        if (prev != graf[curr][0] || graf[curr].size() == 1) {
                            prev = curr;
                            curr = graf[curr][0];
                        } else {
                            prev = curr;
                            lengths[curr] += 2;
                            curr = graf[curr][1];
                        }
                        if (lengths[curr] > 0) {
                            break;
                        }
                        if (curr == dest) {
                            break;
                        }
                    }
                }
            }
            int counting = 0, curr = dest, prev = -1;
            while (true) {
                if (prev != graf[curr][0] || graf[curr].size() == 1) {
                    prev = curr;
                    curr = graf[curr][0];
                } else {
                    prev = curr;
                    curr = graf[curr][1];
                }
                ++counting;
                if (curr == dest) {
                    break;
                }
            }
            vector<int> answers(150010, 0);
            for (int i = 0; i < lengths.size(); ++i) {
                if (lengths[i] > 0) ++answers[lengths[i]];
            }
            for (int i = 0; i < counting; ++i) {
                for (int j = i; j < 150010; j += counting) {
                    if (j > i) {
                        answers[j] += answers[j - counting];
                    }
                }
            }
            for (int it = 0; it < groupCount; ++it) {
                int i = groups[it];
                if (i < 150010) answer(answers[i]);
                else {
                    i -= 150010;
                    i %= counting;
                    i -= counting;
                    i += 150010;
                    answer(answers[i]);
                }
            }
        }

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:77:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for (int i = 0; i < lengths.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~
garden.cpp:42:21: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |                     if (dist < 0) continue;
      |                     ^~

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -