Submission #125146

#	Time	Username	Problem	Language	Result	Execution time	Memory
125146		Masterdan	Werewolf (IOI18_werewolf)	C++14	0 / 100	1568 ms	39184 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define MIN -1
#define MAX 1000000000
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define TAM 100000
typedef vector <int> vi;
vi querys, querys1;
vector <pair <int, int> > rangos, rangos1;
typedef long long int ll;
int v[2*TAM +10];
int v1[TAM+10];
int tree[4*TAM+10];
int tree1[4*TAM+10];
int ters[4*TAM+10];
int aux[2][4*TAM+10];
int n;
int vis1[3010], vis2[3010], vis[3*TAM+10];
vector <vi> G;
vector <vi> G1;
vector <int> v2;
void dfs(int x)
{
    vis[x]=1;
    v2.push_back(x);
    for(int i=0; i<G[x].size (); i++)
    {
        if(vis[G1[x][i]]==0)
        {

            dfs(G1[x][i]);
        }
    }
}
void init(int node, int a, int b)
{
    if(a==b)
    {
        tree[node]=v[a];
        return ;
    }
    init(2*node,a,(a+b)/2);
    init(2*node+1,(a+b)/2+1, b);
    tree[node]=max(tree[2*node], tree[2*node+1]);
}
int query(int node, int a,int b, int p,int q)
{
    if(q<a or b<p)
        return MIN;
    if(p<=a and b<=q)
        return tree[node];
    return max(query(2*node, a, (a+b)/2, p, q), query(2*node+1, (a+b)/2+1, b, p, q));
}
void init1 (int node, int a, int b)
{
    if(a==b)
    {
        tree1[node]=v[a];
        return ;
    }
    init1(2*node, a, (a+b)/2);
    init1(2*node+1, (a+b)/2+1, b);
    tree1[node]=min(tree1[2*node], tree1[2*node+1]);
}
int  query1(int node, int a, int b, int p,int q)
{
    if(q<a or b<p)
        return MAX;
    if(p<=a and b<=q)
        return tree1[node];
    return min(query1(2*node, a, (a+b)/2, p, q), query1(2*node+1, (a+b)/2+1,b,  p, q));
}
void dfs1(int x,int y)
{
    vis1[x]=1;
    for(int i=0; i<G[x].size(); i++)
    {
        if(vis1[G[x][i]]==0 and G[x][i]>=y)
        {
            dfs1(G[x][i], y);
        }
    }
}
void dfs2(int x,int  y)
{
    vis2[x]=1;
    for(int i=0; i<G[x].size(); i++)
    {
        if(vis2[G[x][i]]==0 and G[x][i]<=y)
        {
            dfs2(G[x][i], y);
        }
    }
}
int binary(int s, int e, int L, int R)
{
    if(s<e)
    {
        int l=s;
        int r=e;
        while(l<r)
        {
            int m=(l+r+1)/2;
            if(query1(1, 0, n-1, l, m)<L)
                r=m-1;
            else
                l=m;
        }
        if(query1(1, 0, n-1, s, l)>=L and query(1, 0, n-1, l, e)<= R)
            return 1;
        else
            return 0;
    }
    else
    {
        int l=e;
        int r=s;
        while(l<r)
        {
            int m=(l+r)/2;
            if (query1(1, 0, n-1, m,r)<L)
                l=m+1;
            else
                r=m;
        }
        if (query1(1, 0, n-1, l, s)>=L and query(1, 0, n-1, e, l) <= R)
            return 1;
        else
            return 0;
    }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R)
{
    n=N;
    G=vector <vi>(n+1);
    G1=vector <vi>(n+1);
    for(int i=0; i<X.size (); i++)
    {
        G[X[i]].pb(Y[i]);
        G[Y[i]].pb(X[i]);
        G1[X[i]].pb(Y[i]);
        G1[Y[i]].pb(X[i]);
    }
    int Q = S.size();
    int sw1=0;
    for(int i=0; i<n; i++)
    {
        if(G[i].size ()>=3)
        {
            sw1=1;
            break;
        }
    }
    vector <int> A(Q);
   /* if(sw1==1 )
    {
        vector<int> A(Q);
        for (int k = 0; k < Q; ++k)
        {
            memset(vis1, 0, sizeof vis1);
            memset(vis2, 0, sizeof vis2);
            dfs1(S[k], L[k]);
            dfs2(E[k], R[k]);
            int sw=0;
            for(int i=0; i<n; i++)
            {
                if(vis1[i]==1 and vis2[i]==1)
                {
                    sw=1;
                    break;
                }
            }
            A[k]=sw;
        }
        return A;
    }*/
    /*for(int i=0;i<n;i++){
      if(G1[i].size ()==1){dfs(i);
      break;}
    }
    map <int, int> m, m1;

    for(int i=0;i<v2.size ();i++)v[i]=v2[i];
    for(int i=0;i<v2.size ();i++){
      m[v[i]]=i;
    }
    for(int i=0;i<v2.size ();i++)v1[i]=v2[i];
    for(int i=0;i<v2.size ();i++)m1[v1[i]]=i;
    init(0, 0, n-1);
    init1(0, 0, n-1);
    for(int k=0;k<Q;k++){int r1, r2;
       r1=query(0, 0, n-1, min(m[S[k]],m[E[k]]), max(m[E[k]], m[S[k]]));
       //rangos.pb(mp(min(m[S[k]],m[E[k]]), max(m[E[k]], m[S[k]])));
       r2=query1(0, 0, n-1, (min(m1[S[k]],m1[E[k]])),(max(m1[E[k]], m1[S[k]])));
       rangos1.pb(mp((min(m1[S[k]],m1[E[k]])),((max(m1[E[k]], m1[S[k]])))));
       querys.pb(r1);
       querys1.pb(r2);
       int lobo=0,  human=0;
      if(r2>=L[k])human=1;
      if(r1<=R[k])lobo=1;
      if(human==1 and lobo==1)A[k]=1;
      else{
          if(m[r1]>=(n-1-m1[r2]))A[k]=1;
          else A[k]=0;
      }
    }
    return A;*/
    for (int i=0; i<n; i++)
        aux[0][i]=aux[1][i]=-1;
    for (int i=0; i<X.size(); i++)
    {
        if (aux[0][X[i]] == -1)
            aux[0][X[i]] = Y[i];
        else
            aux[1][X[i]] = Y[i];
        if (aux[0][Y[i]] == -1)
            aux[0][Y[i]] = X[i];
        else
            aux[1][Y[i]] = X[i];
    }
    int node;
    for (node = 0; node < n; node++)
        if(aux[1][node]==-1)
            break;
    v[0] = node;
    ters[node] = 0;
    v[1] = aux[0][node];
    ters[aux[0][node]] = 1;
    for (int i = 2; i < n; i++)
    {
        if (v[i-2] != aux[0][v[i-1]] and aux[0][v[i-1]] != -1)
        {
            v[i] = aux[0][v[i-1]];
            ters[aux[0][v[i-1]]] = i;
        }
        else
        {
            v[i]=aux[1][v[i-1]];
            ters[aux[1][v[i-1]]] = i;
        }
    }
    init(1, 0, n-1);
    init1(1, 0, n-1);
    for(int k=0; k<Q; k++)
    {
        A[k]=binary(ters[S[k]], ters[E[k]],L[k], R[k]);
    }
    return A;
}

/*
namespace
{

int read_int()
{
    int x;
    if (scanf("%d", &x) != 1)
    {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    return x;
}

}  // namespace

int main()
{
    int N = read_int();
    int M = read_int();
    int Q = read_int();
    std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
    for (int j = 0; j < M; ++j)
    {
        X[j] = read_int();
        Y[j] = read_int();
    }
    for (int i = 0; i < Q; ++i)
    {
        S[i] = read_int();
        E[i] = read_int();
        L[i] = read_int();
        R[i] = read_int();
    }

    std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
    //for(int i=0;i<querys.size ();i++)cout<<querys[i]<<" "<<querys1[i]<<" "<<endl;
    for (size_t i = 0; i < A.size(); ++i)
    {
        printf("%d\n", A[i]);
    }
    return 0;
}*/

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int)':
werewolf.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<G[x].size (); i++)
                  ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<G[x].size(); i++)
                  ~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<G[x].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:141:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<X.size (); i++)
                  ~^~~~~~~~~~
werewolf.cpp:214:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<X.size(); i++)
                   ~^~~~~~~~~
werewolf.cpp:149:9: warning: variable 'sw1' set but not used [-Wunused-but-set-variable]
     int sw1=0;
         ^~~

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