Submission #226199

#	Time	Username	Problem	Language	Result	Execution time	Memory
226199		DavidDamian	Werewolf (IOI18_werewolf)	C++11	15 / 100	546 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)
{
    for(int i=0;i<log_n;i++){
        ancestor[i][root]=n;
        ancestor[i][n]=n;
        minPath[i][root]=INT_MAX;
        maxPath[i][root]=-INT_MAX;
        minPath[i][n]=INT_MAX;
        maxPath[i][n]=-INT_MAX;
    }
    dfs(root,-1,0);
    for(int i=1;i<=log_n;i++){
        for(int u=0;u<n;u++){
            ancestor[i][u]=ancestor[i-1][ancestor[i-1][u]];
            minPath[i][u]=(ancestor[i][u]!=n)? min(minPath[i-1][u],minPath[i-1][ancestor[i-1][u]]) : INT_MAX;
            maxPath[i][u]=(ancestor[i][u]!=n)? 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
    int change=1; //You can change your form
    if(lv[T]>lv[S]){
        swap(T,S);
        form=1; //Wolf
    }
    while(S!=T){
        int d=lv[S]-lv[T];
        bool moved=false;
        for(int i=log_n;i>=0;i--){
            if(d & (1<<i)){
                if(form==0){
                    if(minPath[i][S]>=L){
                        S=ancestor[i][S];
                        moved=true;
                    }
                }
                else{
                    if(maxPath[i][S]<=R){
                        S=ancestor[i][S];
                        moved=true;
                    }
                }
            }
        }
        if(moved==false){
            if(change==1 && L<=S && S<=R){
                form=(form+1)%2; //Change form
                change=0; //You cannot do another change
            }
            else return 0;
        }
    }
    return 1;
}
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].push_back(b);
        adjList[b].push_back(a);
    }
    int root;
    for(int i=0;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],T[i],L[i],R[i]));
    }
    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:145: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