Submission #122472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122472	2019-06-28T11:13:57 Z	neki	Werewolf (IOI18_werewolf)	C++14	Compilation error	0 ms	0 KB

werewolf

//#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]);
        //cout << na << " "<< nb << endl;
        cc(ans[i]);
    }
    return ans;
}






















int main() {
	int n, m, q, a, b;cin >> n >>m >>q;
	vector<int> x, y;
	loop(i, 0, m){
	    scanf("%d%d", &a, &b);
	    x.push_back(a);y.push_back(b);
	}
	vector<int> s, e, l, r;int ts, te, tl, tr;
	loop(i, 0, q){
	    scanf("%d%d%d%d", &ts, &te,&tl, &tr);
	    s.push_back(ts);e.push_back(te);l.push_back(tl);r.push_back(tr);
	}
	check_validity(n, x, y, s, e, l, r);
}

Compilation message

werewolf.cpp: In function 'int main()':
werewolf.cpp:134:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &a, &b);
      ~~~~~^~~~~~~~~~~~~~~~
werewolf.cpp:139:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d%d%d", &ts, &te,&tl, &tr);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cctB75Hp.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccurzSqy.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status