oj.uz

Submission #117351

# Submission time Handle Problem Language Result Execution time Memory
117351 2019-06-15T14:28:10 Z Sorting Werewolf (IOI18_werewolf) C++14
100 / 100
 1359 ms 123424 KB 
#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
*/

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17664 KB Output is correct
2 Correct 18 ms 17664 KB Output is correct
3 Correct 17 ms 17664 KB Output is correct
4 Correct 16 ms 17664 KB Output is correct
5 Correct 17 ms 17636 KB Output is correct
6 Correct 17 ms 17664 KB Output is correct
7 Correct 16 ms 17664 KB Output is correct
8 Correct 16 ms 17664 KB Output is correct
9 Correct 16 ms 17664 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17664 KB Output is correct
2 Correct 18 ms 17664 KB Output is correct
3 Correct 17 ms 17664 KB Output is correct
4 Correct 16 ms 17664 KB Output is correct
5 Correct 17 ms 17636 KB Output is correct
6 Correct 17 ms 17664 KB Output is correct
7 Correct 16 ms 17664 KB Output is correct
8 Correct 16 ms 17664 KB Output is correct
9 Correct 16 ms 17664 KB Output is correct
10 Correct 24 ms 19052 KB Output is correct
11 Correct 23 ms 19048 KB Output is correct
12 Correct 24 ms 19052 KB Output is correct
13 Correct 25 ms 19296 KB Output is correct
14 Correct 26 ms 19220 KB Output is correct
15 Correct 24 ms 19168 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 105672 KB Output is correct
2 Correct 832 ms 116736 KB Output is correct
3 Correct 815 ms 114264 KB Output is correct
4 Correct 832 ms 113364 KB Output is correct
5 Correct 820 ms 113356 KB Output is correct
6 Correct 867 ms 113232 KB Output is correct
7 Correct 915 ms 113364 KB Output is correct
8 Correct 828 ms 116552 KB Output is correct
9 Correct 729 ms 114504 KB Output is correct
10 Correct 767 ms 113356 KB Output is correct
11 Correct 804 ms 113340 KB Output is correct
12 Correct 853 ms 113236 KB Output is correct
13 Correct 920 ms 117832 KB Output is correct
14 Correct 1030 ms 117904 KB Output is correct
15 Correct 919 ms 117832 KB Output is correct
16 Correct 915 ms 117820 KB Output is correct
17 Correct 906 ms 113360 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17664 KB Output is correct
2 Correct 18 ms 17664 KB Output is correct
3 Correct 17 ms 17664 KB Output is correct
4 Correct 16 ms 17664 KB Output is correct
5 Correct 17 ms 17636 KB Output is correct
6 Correct 17 ms 17664 KB Output is correct
7 Correct 16 ms 17664 KB Output is correct
8 Correct 16 ms 17664 KB Output is correct
9 Correct 16 ms 17664 KB Output is correct
10 Correct 24 ms 19052 KB Output is correct
11 Correct 23 ms 19048 KB Output is correct
12 Correct 24 ms 19052 KB Output is correct
13 Correct 25 ms 19296 KB Output is correct
14 Correct 26 ms 19220 KB Output is correct
15 Correct 24 ms 19168 KB Output is correct
16 Correct 941 ms 105672 KB Output is correct
17 Correct 832 ms 116736 KB Output is correct
18 Correct 815 ms 114264 KB Output is correct
19 Correct 832 ms 113364 KB Output is correct
20 Correct 820 ms 113356 KB Output is correct
21 Correct 867 ms 113232 KB Output is correct
22 Correct 915 ms 113364 KB Output is correct
23 Correct 828 ms 116552 KB Output is correct
24 Correct 729 ms 114504 KB Output is correct
25 Correct 767 ms 113356 KB Output is correct
26 Correct 804 ms 113340 KB Output is correct
27 Correct 853 ms 113236 KB Output is correct
28 Correct 920 ms 117832 KB Output is correct
29 Correct 1030 ms 117904 KB Output is correct
30 Correct 919 ms 117832 KB Output is correct
31 Correct 915 ms 117820 KB Output is correct
32 Correct 906 ms 113360 KB Output is correct
33 Correct 970 ms 114456 KB Output is correct
34 Correct 363 ms 59632 KB Output is correct
35 Correct 1061 ms 117216 KB Output is correct
36 Correct 932 ms 113880 KB Output is correct
37 Correct 993 ms 116120 KB Output is correct
38 Correct 1027 ms 114516 KB Output is correct
39 Correct 1112 ms 123004 KB Output is correct
40 Correct 1180 ms 122768 KB Output is correct
41 Correct 1063 ms 115832 KB Output is correct
42 Correct 1010 ms 113896 KB Output is correct
43 Correct 1359 ms 120864 KB Output is correct
44 Correct 1077 ms 116320 KB Output is correct
45 Correct 1107 ms 123424 KB Output is correct
46 Correct 1002 ms 123036 KB Output is correct
47 Correct 967 ms 118064 KB Output is correct
48 Correct 1047 ms 118108 KB Output is correct
49 Correct 1038 ms 118060 KB Output is correct
50 Correct 1008 ms 117892 KB Output is correct
51 Correct 1233 ms 123284 KB Output is correct
52 Correct 1236 ms 123344 KB Output is correct