oj.uz

Submission #122473

# Submission time Handle Problem Language Result Execution time Memory
122473 2019-06-28T11:14:33 Z neki Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 297956 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define maxn 200010
#define loop(i, a, b) for(int i=a;i<b;i++)
#define cc(a) cout<< a << endl;


using namespace std;

struct seg{
    map<int, map<int, bool>> tree;
    void update(int x, int y){
        x+=maxn;y+=maxn;
        tree[x][y]=1;
        for(int tx=x;tx>=1;tx>>=1){
            for(int ty=y;ty>=1;ty>>=1) tree[tx][ty]=1;
        }
    }
    bool query(int lx, int ly, int rx, int ry){
        bool ret=0;
        lx+=maxn;ly+=maxn;rx+=maxn;ry+=maxn;
        int slx=lx; int srx=rx;
        for(;slx<srx;slx>>=1, srx>>=1){
            if(slx&1){
                int sly=ly; int sry=ry;
                for(;sly<sry;sly>>=1, sry>>=1){
                    if(sly&1) ret=ret or tree[slx][sly++];
                    if(sry&1) ret=ret or tree[slx][--sry];
                }
                slx++;
            }
            if(srx&1){
                --srx;
                int sly=ly; int sry=ry;
                for(;sly<sry;sly>>=1, sry>>=1){
                    if(sly&1) ret=ret or tree[srx][sly++];
                    if(sry&1) ret=ret or tree[srx][--sry];
                }
            }
        }
        return ret;
    }
};

vector<int> edges[maxn];
int pU[maxn];int pV[maxn];
vector<int> cU[maxn];vector<int> cV[maxn];

int fndU(int u){return (u==pU[u]) ? u:fndU(pU[u]);}
int fndV(int u){return (u==pV[u]) ? u:fndV(pV[u]);}

int eulU[maxn * 2];int eulV[maxn * 2];
int sU[maxn];int eU[maxn];int sV[maxn];int eV[maxn];
int cntU=0;int cntV=0;
void dfsU(int u){
    sU[u]=cntU;eulU[cntU++]=u;
    for(auto&& v:cU[u]) dfsU(v);
    eU[u]=cntU;eulU[cntU++]=u;
}
void dfsV(int u){
    sV[u]=cntV;eulV[cntV++]=u;
    for(auto&& v:cV[u]) dfsV(v);
    eV[u]=cntV;eulV[cntV++]=u;
}

seg r;

int faU(int u, int m){
    if (u==pU[u] or pU[u]>m) return u;
    return faU(pU[u], m);
}
int faV(int u, int m){
    if (u==pV[u] or pV[u]<m) return u;
    return faV(pV[u], m);
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
    int M=X.size();int Q=S.size();
    loop(i, 0, M){edges[X[i]].push_back(Y[i]);edges[Y[i]].push_back(X[i]);}
    loop(i, 0, N) pU[i]=i;loop(i, 0, N) pV[i]=i;
    loop(i, 0, N){
        for(auto&& j: edges[i]){
            if(j>i) continue;
            int pj=fndU(j);
            if(pj==i) continue;
            pU[pj]=i;cU[i].push_back(pj);
        }
    }//disjoint union U
    for(int i=N-1;i>=0;i--){
        for(auto&& j: edges[i]){
            if(j<i) continue;
            int pj=fndV(j);
            if(pj==i) continue;
            pV[pj]=i;cV[i].push_back(pj);
        }
    }//disjoint union V
    dfsU(N-1);dfsV(0);
    loop(i, 0, N) r.update(sU[i], sV[i]);
    vector<int> ans;ans.resize(Q);
    loop(i, 0, Q){
        int na=faV(S[i], L[i]);int nb=faU(E[i], R[i]);
        ans[i]=r.query(sU[nb], sV[na], eU[nb], eV[na]);
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14976 KB Output is correct
2 Correct 18 ms 14976 KB Output is correct
3 Correct 15 ms 14592 KB Output is correct
4 Correct 15 ms 14592 KB Output is correct
5 Correct 18 ms 14976 KB Output is correct
6 Correct 18 ms 14976 KB Output is correct
7 Correct 18 ms 14976 KB Output is correct
8 Correct 21 ms 15020 KB Output is correct
9 Correct 16 ms 15104 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14976 KB Output is correct
2 Correct 18 ms 14976 KB Output is correct
3 Correct 15 ms 14592 KB Output is correct
4 Correct 15 ms 14592 KB Output is correct
5 Correct 18 ms 14976 KB Output is correct
6 Correct 18 ms 14976 KB Output is correct
7 Correct 18 ms 14976 KB Output is correct
8 Correct 21 ms 15020 KB Output is correct
9 Correct 16 ms 15104 KB Output is correct
10 Correct 257 ms 36104 KB Output is correct
11 Correct 256 ms 35196 KB Output is correct
12 Correct 251 ms 31840 KB Output is correct
13 Correct 219 ms 36216 KB Output is correct
14 Correct 256 ms 37112 KB Output is correct
15 Correct 287 ms 32856 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4049 ms 297956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14976 KB Output is correct
2 Correct 18 ms 14976 KB Output is correct
3 Correct 15 ms 14592 KB Output is correct
4 Correct 15 ms 14592 KB Output is correct
5 Correct 18 ms 14976 KB Output is correct
6 Correct 18 ms 14976 KB Output is correct
7 Correct 18 ms 14976 KB Output is correct
8 Correct 21 ms 15020 KB Output is correct
9 Correct 16 ms 15104 KB Output is correct
10 Correct 257 ms 36104 KB Output is correct
11 Correct 256 ms 35196 KB Output is correct
12 Correct 251 ms 31840 KB Output is correct
13 Correct 219 ms 36216 KB Output is correct
14 Correct 256 ms 37112 KB Output is correct
15 Correct 287 ms 32856 KB Output is correct
16 Execution timed out 4049 ms 297956 KB Time limit exceeded
17 Halted 0 ms 0 KB -