제출 #117351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117351		Sorting	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1359 ms	123424 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;
	}

	if(lvalue.type != rvalue.type){
		if(lvalue.type == 2){
			return true;
		}
		if(rvalue.type == 2){
			return false;
		}

		return lvalue.type < rvalue.type;
	}

	return lvalue.y1 < rvalue.y1;
}

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]);

                //cout << "U " << du.par[i] << " " << du.par[to] << endl;

                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]);

                //cout << "V " << dv.par[i] << " " << dv.par[to] << endl;

                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(i, inv[eU[i]]));
   	} 

   	for(int i = 0; i < (int)S.size(); i++){
   		int l1, r1, l2, r2;
   		int s = S[i], e = E[i];

   		for(int j = LOGN - 1; j >= 0; j--){
   			if(upV[s][j] >= L[i]){
   				s = upV[s][j];
   			}
   			if(upU[e][j] <= R[i]){
   				e = upU[e][j]; 
   			}
   		}

   		l2 = tinV[s];
   		r2 = toutV[s];
   		l1 = tinU[e];
   		r1 = toutU[e];

   		//cout << s << " S[I] E[i] " << e << endl;
   		//cout << l2 << " " << r2 << "  - " << l1 << " " << r1 << endl;

   		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);

   	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.y1, 1);
   			continue;
   		}
   	}

   	for(int i = 0; i < ans.size(); i++){
   		int &x = ans[i];

   		if(S[i] < L[i] || E[i] > R[i]){
   			x = 0;
   			continue;
   		}

   		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;
}*/
/*
6 6

5 1
1 2
1 3
3 4
3 0
5 2

3

4 2 1 2
4 2 2 2
5 4 3 4
*/

컴파일 시 표준 에러 (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:146:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                 ~~^~~~~~~~~~
werewolf.cpp:255:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~

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