Submission #200829

#	Time	Username	Problem	Language	Result	Execution time	Memory
200829		ekrem	Bitaro’s Party (JOI18_bitaro)	C++98	0 / 100	12 ms	5112 KiB

bitaro

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 5;
 
priority_queue <vector <int>, vector <vector <int> >, greater <vector <int> > > onesToLook;
 
vector <int> edges[N], children[N], answers;
int visited[N], level[N];
 
int n, m, q, x, y, k, endNode;
 
int longestWay(int node) {
    if (node == endNode)
        return 0;
 
    for (int i = 0; i < children[node].size(); i++) {
        int each = longestWay(children[node][i]);
 
        if (each != -1)
            return each + 1;
    }
 
    return -1;
}
 
int main() {
    cin >> n >> m >> q;
 
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        if (x > y)
            swap(x, y);
        edges[x].push_back(y);
    }
 
    vector <int> first;
    first.push_back(1);
    first.push_back(0);
    first.push_back(-1);
 
    onesToLook.push(first);
 
    while (!onesToLook.empty()) {
        vector <int> currOne = onesToLook.top();
        onesToLook.pop();
 
        if (visited[currOne[0]])
            continue;
 
        visited[currOne[0]] = 1;
 
        if (currOne[2] != -1)
            children[currOne[2]].push_back(currOne[0]);
 
        level[currOne[0]] = currOne[1];
 
 
        for (int i = 0; i < edges[currOne[0]].size(); i++)
            if (!visited[edges[currOne[0]][i]]) {
                vector <int> each;
                each.push_back(edges[currOne[0]][i]);
                each.push_back(level[currOne[0]] - 1);
                each.push_back(currOne[0]);
                onesToLook.push(each);
            }
    }
 
    while (q--) {
        int isThereAns = 0, i = 1;
 
        cin >> endNode >> k;
 
        for (int j = 0; j < k; j++) {
            cin >> x;
             
            for (; i < x && !isThereAns; i++) {
                int ans = longestWay(i);
 
                if (ans != -1) {
                    answers.push_back(ans);
                    isThereAns = 1;
                    break;
                }
            }
 
            i = x+1;
        }
 
        for (; i <= n && !isThereAns; i++) {
            int ans = longestWay(i);
 
            if (ans != -1) {
                answers.push_back(ans);
                isThereAns = 1;
                break;
            }
        }
 
        if (!isThereAns)
            answers.push_back(-1);
    }
 
    for (int i = 0; i < answers.size(); i++)
        cout << answers[i] << endl;
 
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int longestWay(int)':
bitaro.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < children[node].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < edges[currOne[0]].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < answers.size(); i++)
                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86