Submission #417983

#	Time	Username	Problem	Language	Result	Execution time	Memory
417983		LouayFarah	Werewolf (IOI18_werewolf)	C++14	0 / 100	427 ms	28044 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
vector<vector<int>> adj;
vector<int> em;
vector<int> path;
vector<pair<int, int>> sorted_path;
 
void bfs(int n, int S, int E)
{
    vector<bool> visited(n, false);
    vector<int> parent(n, -1);
    queue<int> q;
 
    q.push(S);
    bool flag = true;
    visited[S] = true;
 
    while(!q.empty()&&flag)
    {
        int u = q.front();
        q.pop();
 
        visited[u] = true;
 
        for(auto v: adj[u])
        {
            if(visited[v])
                continue;
            parent[v] = u;
            q.push(v);
            if(v==E)
                flag = false;
        }
    }
 
    vector<int> p;
    int x = E;
    while(x!=-1)
    {
        p.pb(x);
        x = parent[x];
    }
 
    reverse(p.begin(), p.end());
    path = p;
}
 
int bs(int x)
{
    int l = 0, r = (int)sorted_path.size();
    while(l<=r)
    {
        int mid = l + (r-l)/2;
        if(sorted_path[mid].fi==x)
            return sorted_path[mid].se;
        if(sorted_path[mid].fi<x)
            l = mid+1;
        else
            r = mid-1;
    }
    return -1;
}
 
const int Q = 200000;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
    int m = (int)x.size();
    int q = (int)l.size();
    vector<int> res(q, 0);
 
    adj.assign(n, em);
 
    pair<int, int> boundary  = mp(-1, -1);
    for(int i  = 0; i<m; i++)
    {
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
 
    for(int i = 0; i<n; i++)
    {
        if((int)adj[i].size()==1)
        {
            if(boundary.fi==-1)
                boundary.fi = i;
            else
            {
                boundary.se = i;
                break;
            }
        }
    }
 
    bfs(n, boundary.fi , boundary.se);
    int len = int(path.size());
 
    for(int i = 0; i<len; i++)
    {
        sorted_path.pb(mp(path[i], i));
    }
    sort(sorted_path.begin(), sorted_path.end());
 
    for(int querie = 0; querie<q; querie++)
    {
        int S = s[querie];
        int E = e[querie];
        int L = l[querie];
        int R = r[querie];
 
        bool flag = false;
        bool reversed = false;
 
        int ind_start = bs(S);
        int ind_end = bs(E);
        if(ind_end<ind_start)
            reversed = true;
 
        if(reversed)
        {
            int i = ind_start;
            int last = ind_start;
            while(i>ind_end)
            {
                if(path[i]>=L&&path[i]<=R)
                    last = i;
                if(path[i]<L)
                    break;
                i--;
            }
 
            if(i==ind_end)
                flag = true;
            else
            {
                i = last -1;
                while(i>ind_end)
                {
                    if(path[i]>R)
                        break;
                    i--;
                }
                if(i==ind_end)
                    flag = true;
            }
        }
        else
        {
            int i = ind_start;
            int last = ind_start;
            while(i<ind_end)
            {
                if(path[i]>=L&&path[i]<=R)
                    last = i;
                if(path[i]<L)
                    break;
                i++;
            }
 
            i = last + 1;
            while(i<ind_end)
            {
                if(path[i]>R)
                    break;
                i++;
            }
            if(i==ind_end)
                flag = true;
        }
 
        if(flag)
            res[querie] = 1;
        else
            res[querie] = 0;
    }
    return res;
}

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