Submission #117286

#	Time	Username	Problem	Language	Result	Execution time	Memory
117286		Sorting	늑대인간 (IOI18_werewolf)	C++14	0 / 100	748 ms	192116 KiB

werewolf

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 2e5 + 7;
const int LOGN = 20;

struct dsu{
    int par[MAXN], cnt[MAXN];
    
    dsu(){
    	for(int i = 0; i < MAXN; i++){
            par[i] = i;
            cnt[i] = 1;
        }
    }
    
    void find_par(int u){
        if(u == par[u]){
            return;
        }
        
        find_par(par[u]);
        par[u] = par[par[u]];
    }
};
 
dsu du, dv;
 
vector<int> adj[MAXN], ans;
vector<int> U[MAXN], V[MAXN];

int tinU[MAXN], tinV[MAXN];
int toutU[MAXN], toutV[MAXN];
vector<int> eU, eV, inv;

int upU[MAXN][LOGN], upV[MAXN][LOGN];

void dfsU(int u, int p){
	eU.push_back(u);
	tinU[u] = (int)eU.size() - 1;
	upU[u][0] = p; 

	for(int to: U[u]){
		if(to == p){
			continue;
		}

		dfsU(to, u);
		//eU.push_back(u);
	}

	toutU[u] = (int)eU.size() - 1;
}

void dfsV(int u, int p){
	eV.push_back(u);
	tinV[u] = (int)eV.size() - 1;
	upV[u][0] = p;

	for(int to: V[u]){
		if(to == p){
			continue;
		}

		dfsV(to, u);
		//eV.push_back(u);
	}

	toutV[u] = (int)eV.size() - 1;
} 

int fenwick[MAXN];

void update_fenwick(int idx, int delta){
	idx++;

	for(; idx < MAXN; idx += (idx & -idx)){
		fenwick[idx] += delta;
	}
}

int query_fenwick(int idx){
	int ret = 0;
	idx++;

	for(; idx >= 1; idx  -= (idx & -idx)){
		ret += fenwick[idx];
	}

	return ret;
}

int range_fenwick(int l, int r){
	if(l == 0){
		return query_fenwick(r);
	}

	return query_fenwick(r) - query_fenwick(l - 1);
}

struct query{
	short type;
	int x, y1, y2, idx;

	query(){}
	query(int x, int y){
		type = 2;
		this->x = x;
		y1 = y;
		y2 = -1;
		idx = -1;
	}
	query(int x, int y1, int y2, short type, int idx){
		this->type = type;
		this->x = x;
		this->y1 = y1;
		this->y2 = y2;
		this->idx = idx;
	}
};

bool cmp(query lvalue, query rvalue){
	if(lvalue.x != rvalue.x){
		return lvalue.x < rvalue.x;
	}
}

vector<query> q;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){

	for(int i = 0; i < X.size(); i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

    for(int i = 0; i < N; i++){
        for(int to: adj[i]){
            if(to < i){
            	du.find_par(i);
            	du.find_par(to);

            	if(du.par[i] == du.par[to]){
            		continue;
            	}

                U[ du.par[i] ].push_back(du.par[to]);
                U[ du.par[to] ].push_back(du.par[i]);

                du.par[du.par[to]] = du.par[i];
            }
        }
    }
    dfsU(N - 1, N - 1);
    
    for(int i = N - 1; i >= 0; i--){
        for(int to: adj[i]){
            if(to > i){
                dv.find_par(i);
            	dv.find_par(to);

            	if(dv.par[i] == dv.par[to]){
            		continue;
            	}

                V[ dv.par[i] ].push_back(dv.par[to]);
                V[ dv.par[to] ].push_back(dv.par[i]);

                dv.par[dv.par[to]] = dv.par[i];
            }
        }
    }
    dfsV(0, 0);

    for(int j = 1; j < LOGN; j++){
    	for(int i = 0; i < N; i++){
    		upU[i][j] = upU[upU[i][j - 1]][j - 1];
    		upV[i][j] = upV[upV[i][j - 1]][j - 1];
    	}
    }

    for(int i = 0; i < N; i++){
    	inv.push_back(0);
    }

   	for(int i = 0; i < N; i++){
   		inv[eV[i]] = i;
   	}

   	for(int i = 0; i < N; i++){
   		q.push_back(query(eU[i], inv[i]));
   	}

   	for(int i = 0; i < (int)S.size(); i++){
   		int l1, r1, l2, r2;

   		l2 = tinV[S[i]];
   		r2 = toutV[S[i]];
   		l1 = tinU[E[i]];
   		r1 = toutU[E[i]];

   		q.push_back(query(l1 - 1, l2, r2, 0, i));
   		q.push_back(query(r1, l2, r2, 1, i));
   		ans.push_back(0);
   	}

   	sort(q.begin(), q.end(), cmp);

   	return ans;

   	for(query t: q){
   		if(t.type == 0){
   			ans[t.idx] -= range_fenwick(t.y1, t.y2);
   			continue;
   		}
   		if(t.type == 1){
   			ans[t.idx] += range_fenwick(t.y1, t.y2);
   			continue;
   		}
   		if(t.type == 2){
   			update_fenwick(t.x, 1);
   			continue;
   		}
   	}


   	for(int &x: ans){
   		if(x > 0){
   			x = 1;
   		}
   		else{
   			x = 0;
   		}
   	}
   
    return ans;
}
 
/*vector<int> xv, yv, sv, ev, lv, rv, res;
 
int main(){
	int n, m;
 
	cin >> n >> m;
 
	for(int i = 0; i < m; i++){
		int x, y;
 
		cin >> x >> y;
 
		xv.push_back(x);
		yv.push_back(y);
	}
 
	int q;
 
	cin >> q;
 
	for(int i = 0; i < q; i++){
		int sx, ex, lx, rx;
 
		cin >> sx >> ex >> lx >> rx;
 
		sv.push_back(sx);
		ev.push_back(ex);
		lv.push_back(lx);
		rv.push_back(rx);
	}
 
	res = check_validity(n, xv, yv, sv, ev, lv, rv);
 
	for(int t: res){
		if(t > 0){
			cout << "1 ";
		}
		else{
			cout << "0 ";
		}
	}
	cout << endl;
 
	return 0;
}*/
/*
3 3
0 1
0 2
2 1
2
0 1 1 1
1 0 1 2
*/

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:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                 ~~^~~~~~~~~~
werewolf.cpp: In function 'bool cmp(query, query)':
werewolf.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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