Submission #226205

#	Time	Username	Problem	Language	Result	Execution time	Memory
226205		DavidDamian	Werewolf (IOI18_werewolf)	C++11	15 / 100	611 ms	76784 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///Record ancestors
///Move through the graph greedily
vector<int> adjList[200005];
int destiny;
int color[6005];
int c=0;
int n;
int l,r;
int lv[200005];
int ancestor[20][200005];
int minPath[20][200005]; //Min and max in path
int maxPath[20][200005];
void dfs(int u,int e,int depth)
{
    lv[u]=depth;
    for(int v: adjList[u]){
        if(v==e) continue;
        ancestor[0][v]=u;
        minPath[0][v]=u;
        maxPath[0][v]=u;
        dfs(v,u,depth+1);
    }
}
int dfsVisit(int u)
{
    if(u==destiny) return 1;
    int ans=0;
    color[u]=c;
    for(int v: adjList[u]){
        if(ans==1) break;
        if(color[v]!=c){
            if(v!=u+n){
                if(v<n && v>=l)
                    ans=dfsVisit(v);
                if(v>=n && v<=r+n)
                    ans=dfsVisit(v);
            }
            if(v==u+n && l<=u && u<=r)
                ans=dfsVisit(v);
        }
    }
    return ans;
}
#define log_n 18
void buildAncestor(int root)
{
    minPath[0][root]=INT_MAX;
    maxPath[0][root]=-INT_MAX;
    dfs(root,0,0);
    for(int i=1;i<=log_n;i++){
        for(int u=1;u<=n;u++){
            ancestor[i][u]=ancestor[i-1][ancestor[i-1][u]];
            minPath[i][u]=(ancestor[i][u]!=0)? min(minPath[i-1][u],minPath[i-1][ancestor[i-1][u]]) : INT_MAX;
            maxPath[i][u]=(ancestor[i][u]!=0)? max(maxPath[i-1][u],maxPath[i-1][ancestor[i-1][u]]) : -INT_MAX;
        }
    }
}
#define debug(x) cout<<#x<<" = "<<x<<endl
int possible(int S,int T,int L,int R)
{
    int form=0; //Human
    if(lv[T]>lv[S]){
        swap(T,S);
        form=1; //Wolf
    }
    int u=S;
    for(int b=log_n;b>=0;b--){
        if(ancestor[b][u]==0) continue;
        if(form==0){
            if(minPath[b][u]>=L)
                u=ancestor[b][u];
        }
        else{
            if(maxPath[b][u]<=R)
                u=ancestor[b][u];
        }
    }
    if(lv[ ancestor[0][u] ]<=lv[T]) return 1;
    if(L<=u && u<=R) form=(form+1)%2;
    for(int b=log_n;b>=0;b--){
        if(ancestor[b][u]==0) continue;
        if(form==0){
            if(minPath[b][u]>=L)
                u=ancestor[b][u];
        }
        else{
            if(maxPath[b][u]<=R)
                u=ancestor[b][u];
        }
    }
    if(lv[ ancestor[0][u] ]<=lv[T]) return 1;
    else return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
    int m=X.size();
    int Q=S.size();
    n=N;
    if(n<=3000){
        for(int i=0;i<m;i++){
            int a=X[i];
            int b=Y[i];
            adjList[a].push_back(b);
            adjList[b].push_back(a);
            adjList[a+n].push_back(b+n);
            adjList[b+n].push_back(a+n);
        }
        for(int i=0;i<n;i++){
            adjList[i].push_back(i+n);
        }
        vector<int> A;
        for(int i=0;i<Q;i++){
            c++;
            destiny=T[i]+n;
            l=L[i];
            r=R[i];
            A.push_back(dfsVisit(S[i]));
        }
        return A;
    }
    for(int i=0;i<m;i++){
        int a=X[i];
        int b=Y[i];
        adjList[a+1].push_back(b+1);
        adjList[b+1].push_back(a+1);
    }
    int root;
    for(int i=1;i<=n;i++){
        if(adjList[i].size()==1){
            root=i;
            break;
        }
    }
    buildAncestor(root);
    vector<int> A;
    for(int i=0;i<Q;i++){
        A.push_back(possible(S[i]+1,T[i]+1,L[i]+1,R[i]+1));
    }
    return A;
}

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:137:18: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     buildAncestor(root);
     ~~~~~~~~~~~~~^~~~~~

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