oj.uz

Submission #138157

# Submission time Handle Problem Language Result Execution time Memory
138157 2019-07-29T13:29:25 Z Lawliet Werewolf (IOI18_werewolf) C++14
15 / 100
 201 ms 19744 KB 
#include <bits/stdc++.h>

#define MAX 3010

using namespace std;

class DisjointSetUnion
{
	public:

		int find(int i, int t)
		{
			if(pai[i] == i) return i;
			if(version[i] > t) return i;
			return find(pai[i] , t);
		}

		void join(int i, int j)
		{
			i = find(i , curTime); j = find(j , curTime);

			if(i == j) return;

			if(peso[i] < peso[j]) swap(i , j);

			pai[j] = i;
			version[j] = curTime;

			if(peso[i] == peso[j]) peso[i]++;
		}	

		bool same(int i, int j, int k) { return find(i , k) == find(j , k); }

		void init(int N)
		{
			for(int g = 0 ; g < N ; g++)
			{
				pai[g] = g;
				peso[g] = 0;
				version[g] = -1;
			}

			curTime = 0;
		}

		void updateVersion() { curTime++; }

	private:

		int curTime;

		int pai[MAX];
		int peso[MAX];
		int version[MAX];
};

int N, M, Q;

vector<int> ans;

vector<int> grafo[MAX];

DisjointSetUnion prefix, suffix;

void makeDSU()
{
	prefix.init( N );
	suffix.init( N );

	for(int g = 0 ; g < N ; g++)
	{
		for(int h = 0 ; h < grafo[ g ].size() ; h++)
		{
			int prox = grafo[g][h];

			if(prox < g) prefix.join(g , prox);
		}

		prefix.updateVersion( );
	}

	//printf("=======================================\n");

	for(int g = N - 1 ; g >= 0 ; g--)
	{
		for(int h = 0 ; h < grafo[ g ].size() ; h++)
		{
			int prox = grafo[g][h];

			if(prox > g) suffix.join(g , prox);
		}

		suffix.updateVersion( );
	}
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
	N = n; M = X.size(); Q = L.size();

	for(int g = 0 ; g < M ; g++)
	{
		int i = X[g];
		int j = Y[g];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );
	}

	makeDSU();

	for(int curQuery = 0 ; curQuery < Q ; curQuery++)
	{
		bool canTransform = false;

		for(int transform = L[ curQuery ] ; transform <= R[ curQuery ] && !canTransform ; transform++)
		{
			//printf("curQuery = %d     %d  %d\n",curQuery,transform,canTransform);
			if(!prefix.same(transform , E[ curQuery ] , R[ curQuery ])) continue;
			//printf("passei\n");

			if(suffix.same(transform , S[ curQuery ] , N - L[ curQuery ] - 1)) canTransform = true;
		}

		if(canTransform) ans.push_back( 1 );
		else ans.push_back( 0 );

		//printf("\n\n");
	}

	return ans;
}

/*int main()
{
	int nn, qq, mm;
	scanf("%d %d %d",&nn,&mm,&qq);

	vector<int> xx(mm), yy(mm);
	vector<int> ss(qq), ee(qq), ll(qq), rr(qq);

	for(int g = 0 ; g < mm ; g++)
		scanf("%d %d",&xx[g],&yy[g]);

	for(int g = 0 ; g < qq ; g++)
		scanf("%d %d %d %d",&ss[g],&ee[g],&ll[g],&rr[g]);

	vector<int> final = check_validity(nn , xx , yy , ss , ee , ll , rr);

	for(int g = 0 ; g < qq ; g++)
		printf("%d ",final[g]);
}*/

Compilation message

werewolf.cpp: In function 'void makeDSU()':
werewolf.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < grafo[ g ].size() ; h++)
                   ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < grafo[ g ].size() ; h++)
                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 404 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 404 KB Output is correct
10 Correct 28 ms 780 KB Output is correct
11 Correct 44 ms 752 KB Output is correct
12 Correct 81 ms 764 KB Output is correct
13 Correct 19 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 145 ms 996 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 ms 19744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 404 KB Output is correct
10 Correct 28 ms 780 KB Output is correct
11 Correct 44 ms 752 KB Output is correct
12 Correct 81 ms 764 KB Output is correct
13 Correct 19 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 145 ms 996 KB Output is correct
16 Runtime error 201 ms 19744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -