Submission #226650

#	Time	Username	Problem	Language	Result	Execution time	Memory
226650		AaronNaidu	Werewolf (IOI18_werewolf)	C++14	49 / 100	1713 ms	225992 KiB

werewolf

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

vector<int> graph[2000001];
vector<bool> worksFromStart, worksFromEnd;
queue<int> q;
vector<int> x, y, s, e, l, r;
int n;
int posOfCity[2000001];
int cityAtPos[2000001];
vector<int> maxRange[2100001];
vector<int> minRange[2100001];

int getMax(int start, int finish) {
    int range = finish - start + 1;
    int index = log2(range);
    return max(maxRange[start][index], maxRange[finish - (int) pow(2, index) + 1][index]);
}

int getMin(int start, int finish) {
    int range = finish - start + 1;
    int index = log2(range);
    return min(minRange[start][index], minRange[finish - (int) pow(2, index) + 1][index]);
}

int doQuery(int x) {
    //cout << "Doing query " << x << "\n";
    //return 1;
    int minn = min(posOfCity[s[x]], posOfCity[e[x]]);
    int maxx = max(posOfCity[s[x]], posOfCity[e[x]]);
    int start = minn;
    int finish = maxx;
    //return 1;
    while (minn <= maxx)
    {
        //cout << "Min is " << minn << " and maxx is " << maxx << "\n";
        int med = (minn + maxx)/2;
        if (posOfCity[s[x]] < posOfCity[e[x]])
        {
            if (getMin(start, med) >= l[x])
            {
                if (getMax(med, finish) <= r[x])
                {
                    //cout << "Works\n";
                    return 1;
                }
                minn = med + 1;
            }
            else
            {
                if (getMax(med, finish) <= r[x])
                {
                    maxx = med - 1;
                }
                else
                {
                    //cout << "Fails\n";
                    return 0;
                }
                
            }
        }
        else
        {
            if (getMax(start, med) <= r[x])
            {
                if (getMin(med, finish) >= l[x])
                {
                    //cout << "Reverse works\n";
                    return 1;
                }
                minn = med + 1;
            }
            else
            {
                if (getMin(med, finish) >= l[x])
                {
                    maxx = med - 1;
                }
                else
                {
                    //cout << "Reverse fails\n";
                    return 0;
                }
                
            }
            
        }
        
    }
    return 0;
}

void startsAt(int node) {
    posOfCity[node] = 0;
    cityAtPos[0] = node;
    cityAtPos[1] = graph[node][0];
    posOfCity[graph[node][0]] = 1;
    for (int i = 2; i < n; i++)
    {
        if (graph[cityAtPos[i-1]][0] == cityAtPos[i-2])
        {
            cityAtPos[i] = graph[cityAtPos[i-1]][1];
            posOfCity[cityAtPos[i]] = i;
        }
        else
        {
            cityAtPos[i] = graph[cityAtPos[i-1]][0];
            posOfCity[cityAtPos[i]] = i;
        } 
    }
}

vector<int> straight_line() {
    for (int i = 0; i < x.size(); i++)
    {
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }
    for (int i = 0; i < n; i++)
    {
        if (graph[i].size() == 1)
        {
            //cout << "Starts at " << 
            startsAt(i);
            break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        minRange[i].push_back(cityAtPos[i]);
        maxRange[i].push_back(cityAtPos[i]);
        //cout << maxRange[i][0] << "\t";
    }
    //cout << "\n";
    for (int i = 1; i < 20; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (minRange[j + (int) pow(2, i-1)].size() == i)
            {
                minRange[j].push_back( min(minRange[j][i-1], minRange[j + (int) pow(2, i-1)][i-1]) );
                maxRange[j].push_back( max(maxRange[j][i-1], maxRange[j + (int) pow(2, i-1)][i-1]) );
                //cout << maxRange[j][i] << "\t";
            }
        }
       // cout << "\n";
    }
    //cout << "Here";
    vector<int> toRet;
    //cout << "Going in\n";
    for (int i = 0; i < s.size(); i++)
    {
        toRet.push_back(doQuery(i));
    }
    return toRet;
}

vector<int> check_validity(int ln, vector<int> lx, vector<int> ly, vector<int> ls, vector<int> le, vector<int> ll, vector<int> lr) {
    n = ln;
    x = lx;
    y = ly;
    s = ls;
    e = le;
    l = ll;
    r = lr;
    if (n > 3000 or x.size() > 6000 or s.size() > 3000)
    {
        return straight_line();
    }
    
    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> straight_line()':
werewolf.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
werewolf.cpp:141:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (minRange[j + (int) pow(2, i-1)].size() == i)
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
werewolf.cpp:153:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~
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:174:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
werewolf.cpp:182: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: 34 / 34
• Subtask 4: 0 / 51