oj.uz

Submission #138152

# Submission time Handle Problem Language Result Execution time Memory
138152 2019-07-29T13:26:57 Z Lawliet Werewolf (IOI18_werewolf) C++14
7 / 100
 4000 ms 19832 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;
		}	

		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 ] ; 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:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < grafo[ g ].size() ; h++)
                   ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:84: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 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Execution timed out 4065 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 ms 19832 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 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 372 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Execution timed out 4065 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -