Задача „Стрелки“

http://mendo.mk/Task.do?id=794

Help. Од првите 4 тест примери само 4ти ми е точен, а кога ги симнав пример 1 и 2 од Мендо output ми е како што треба, а ми ги смета за неточни. Зошто?

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <list>
#include <cstring>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <cstdlib>
#include <string>
#include <iomanip>
#include <climits>

#define pb push_back
#define mk make_pair
#define MINE min_element
#define MAXE max_element

using namespace std;

const int MAXN = 100;
const int MAXH = 100000;
const int MAXV = 1000000000;
const long long MAXL = 1000000000000;

vector <vector <int> > graph(MAXN);
struct state {
    int n;
    string s;
};
vector <state> answers;

void bfs(int start, int n) {
    queue <int> q;
    q.push(start);
    int last;
    vector <bool> visited(n, false);
    visited[start] = true;

while (!q.empty()) {
        int node = q.front();
        q.pop();

for (auto next : graph[node]) {
            if (visited[next]) {
                answers.pb({-1, "CIKLUS"});
                return ;
            }
            visited[next] = true;
            q.push(next);
            last = next;
        }
    }
    answers.pb({last, ""});
}

int main() {
    int n;
    cin >> n;

graph = vector <vector <int> > (n+1);
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (a != 0) graph[i].pb(a);
    }

int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;

if (a == 2) {
            graph[b].erase(graph[b].begin());
        }
        else {
            bfs(b, n);
        }
    }

for (auto i : answers) {
        if (i.n >= 0) cout << i.n;
        else cout << i.s;
        cout << endl;
    }

return 0;
}

Тест пример 1 симнат од Мендо:

input:
10
0 4 0 8 9 7 10 1 0 3
10
1 5
1 8
1 8
1 10
1 3
1 5
1 4
1 1
1 2
1 5
output:
9
1
1
3
3
9
1
1
1
9
MY OUTPUT:
9
1
1
3
3
9
1
1
1
9

А не ми дава поени за тој тест пример.

Второ прашање: Овој код очигледно надминува временски лимит за многу примери, како да го оптимизирам?

floreloriz123 wrote:http://mendo.mk/Task.do?id=794

Help. Од првите 4 тест примери само 4ти ми е точен, а кога ги симнав пример 1 и 2 од Мендо output ми е како што треба, а ми ги смета за неточни. Зошто?

А не ми дава поени за тој тест пример.

Не сум на компјутер да проверам, ама еден од проблемите може да е тоа што имаш неиницијализирани променливи - на пример, види ја линија 39, стави таму нешто како (int last = 1) или некоја вредност.
Може да има и други проблеми, малку е тешко да се види од телефон.

petarsor wrote:Не сум на компјутер да проверам, ама еден од проблемите може да е тоа што имаш неиницијализирани променливи - на пример, види ја линија 39, стави таму нешто како (int last = 1) или некоја вредност.

Пробав, не е до тоа грешката.

floreloriz123 wrote:

petarsor wrote:Не сум на компјутер да проверам, ама еден од проблемите може да е тоа што имаш неиницијализирани променливи - на пример, види ја линија 39, стави таму нешто како (int last = 1) или некоја вредност.

Пробав, не е до тоа грешката.

Мислам дека не си пробал, инаку ќе откриеше каде сакав да те насочам, ама добро - ќе бидам уште попрецизен. Смени ја оваа линија

со оваа линија

И прати го така решението на Мендо. Ќе помине на тие примери.
Исто, можеш да размислиш (мада не е тоа проблемот во овој случај) да ја смениш линија 40 (дали треба n таму?).

Аха, така работи. А зошто не работи ако не е иницијализирана, кога нема грешки при компајлирање и одговорот што се бара е исти?

floreloriz123 wrote:Аха, така работи. А зошто не работи ако не е иницијализирана, кога нема грешки при компајлирање и одговорот што се бара е исти?

Бидејќи немаш доделено вредност на променливата, не знаеш што се наоѓа на таа локација во меморијата, па програмата може да дава различни резултати на различни компјутери. На пример, јас имам два компјутера, и на двата твојата програма не дава точен резултат. (Верувам дека кај тебе може да е различно, или да не си приметил дека има разлики во резултатите оти излезот е подолг).
Можеш повеќе да прочиташ тука: http://mendo.mk/Lecture.do?id=21