Submission #226634

#	Time	Username	Problem	Language	Result	Execution time	Memory
226634		AaronNaidu	Werewolf (IOI18_werewolf)	C++14	15 / 100	333 ms	32908 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[100001];
vector<bool> worksFromStart, worksFromEnd;
queue<int> q;

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    vector<int> toRet;
    for (int i = 0; i < x.size(); i++)
    {
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }
    worksFromStart.resize(n);
    worksFromEnd.resize(n);
    //visited.resize(n);
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < n; j++)
        {
            worksFromStart[j] = false;
            worksFromEnd[j] = false;
            //visited[j] = false;
        }
        worksFromStart[s[i]] = true;
        q.push(s[i]);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (auto j : graph[x])
            {
                if (!worksFromStart[j] and j >= l[i])
                {
                    worksFromStart[j] = true;
                    q.push(j);
                }
                
            }
            
        }
        worksFromEnd[e[i]] = true;
        q.push(e[i]);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (auto j : graph[x])
            {
                if (!worksFromEnd[j] and j <= r[i])
                {
                    worksFromEnd[j] = true;
                    q.push(j);
                }
                
            }
        }    
        bool works = false;
        for (int j = 0; j < n; j++)
        {
            if (worksFromStart[j] and worksFromEnd[j])
            {
                //cout << "Change at " << j << "\n";
                works = true;
                break;
            }
            
        }
        toRet.push_back(works);
    }
    return toRet;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:10:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
werewolf.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51