oj.uz

Submission #44134

# Submission time Handle Problem Language Result Execution time Memory
44134 2018-03-30T08:07:13 Z zigui Pictionary (COCI18_pictionary) C++17
140 / 140
 326 ms 27008 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4132 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7864 KB Output is correct
2 Correct 40 ms 7864 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11144 KB Output is correct
2 Correct 52 ms 11144 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 11144 KB Output is correct
2 Correct 75 ms 11144 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 12640 KB Output is correct
2 Correct 104 ms 12640 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 16192 KB Output is correct
2 Correct 132 ms 16192 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 16192 KB Output is correct
2 Correct 230 ms 19956 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 22744 KB Output is correct
2 Correct 268 ms 22744 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 27008 KB Output is correct
2 Correct 300 ms 27008 KB Output is correct