oj.uz

Submission #138155

# Submission time Handle Problem Language Result Execution time Memory
138155 2019-07-29T13:28:33 Z Lawliet Werewolf (IOI18_werewolf) C++14
7 / 100
 4000 ms 19708 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 ] && !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: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 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct

Subtask #2
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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 930 ms 772 KB Output is correct
11 Correct 729 ms 888 KB Output is correct
12 Correct 124 ms 900 KB Output is correct
13 Correct 3957 ms 1108 KB Output is correct
14 Execution timed out 4078 ms 888 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 19708 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 930 ms 772 KB Output is correct
11 Correct 729 ms 888 KB Output is correct
12 Correct 124 ms 900 KB Output is correct
13 Correct 3957 ms 1108 KB Output is correct
14 Execution timed out 4078 ms 888 KB Time limit exceeded
15 Halted 0 ms 0 KB -