Submission #44134

#	Time	Username	Problem	Language	Result	Execution time	Memory
44134		zigui	Pictionary (COCI18_pictionary)	C++17	140 / 140	326 ms	27008 KiB

pictionary

#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4N2N26)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define Se second
#define Fi first
#define rep(i, n) for(int i=0;i<n;i++)
#define pb(x) push_back(x)

const int MX = 100005;
const int MM = 1000000433;

int L[MX], R[MX];
int A[MX], B[MX];
vector<int> Qv[MX];

struct UF{
	int t[MX];
	int find(int x){ return t[x] != x ? t[x] = find(t[x]): x; }
	int merge(int a, int b){ t[find(a)] = find(b); }
}uf;

int main()
{
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	for(int i = 1; i <= Q; i++){
		scanf("%d%d", A+i, B+i);
		L[i] = 1, R[i] = M;
	}
	
	while(1){
		int ch = 0;
		for(int i = 1; i <= M; i++) Qv[i].clear();
		for(int i = 1; i <= N; i++) uf.t[i] = i;
		for(int i = 1; i <= Q; i++){
			if(L[i] <= R[i]) Qv[(L[i]+R[i])/2].push_back(i), ch = 1;
		}
		if(ch == 0) break;
		for(int i = 1; i <= M; i++){
			int v = M-i+1;
			for(int j = 2*v; j <= N; j += v) uf.merge(v, j);
			
			for(int ad : Qv[i]){
				if(uf.find(A[ad]) == uf.find(B[ad])) R[ad] = i-1;
				else L[ad] = i+1;
			}
		}
	}
	for(int i = 1; i <= Q; i++) printf("%d\n", L[i]);
}

Compilation message (stderr)

pictionary.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4N2N26)
 
pictionary.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")
 
pictionary.cpp: In member function 'int UF::merge(int, int)':
pictionary.cpp:63:49: warning: no return statement in function returning non-void [-Wreturn-type]
  int merge(int a, int b){ t[find(a)] = find(b); }
                                                 ^
pictionary.cpp: In function 'int main()':
pictionary.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14