oj.uz

답안 #558425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558425 2022-05-07T09:49:44 Z fatemetmhr City (JOI17_city) C++17
8 / 100
 459 ms 49852 KB 
// Be name khoda //

#include <bits/stdc++.h>
#include "Encoder.h"

using namespace std;

typedef long long ll;

#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 5e5 + 10;
const int maxnt = 4e5 + 10;

static ll code[maxn5], sz[maxn5], av[maxn5];
static vector <int> adj[maxn5];

static bool cmp(int v, int u){
	return sz[v] > sz[u];
}


static void dfs_det(int v, int par){
	sz[v] = 1;
	for(auto u : adj[v]) if(u != par){
		dfs_det(u, v);
		sz[v] += sz[u];
	}
	return;
}

static void dfs_code(int v, int par, int pt){
	code[v] = av[v] + (1LL << pt);
	if(adj[v].size() == 1 && v)
		return;
	sort(all(adj[v]), cmp);
	int done = 0;
	for(auto u : adj[v]) if(u != par){
		done++;
		if(done == adj[v].size() - 1 + (v == 0)){
			if(done == 1){
				av[u] = av[v];
				dfs_code(u, v, pt + 1);
				break;
			}
			av[u] = av[v];
			dfs_code(u, v, pt);
			break;
		}
		av[u] = av[v] + (1LL << pt);
		pt++;
		dfs_code(u, v, pt);
	}
	return;
}

void Encode(int N, int A[], int B[])
{

	for(int i = 0; i < N - 1; i++){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}

	dfs_det(0, -1);
	dfs_code(0, -1, 0);

	for (int i = 0; i < N; ++i) {
		Code(i, code[i]);
	}
}

// Be name khoda //

#include <bits/stdc++.h>
#include "Device.h"

using namespace std;

typedef long long ll;


#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 4e3 + 10;
const int maxnt = 4e5 + 10;

void InitDevice()
{
	return;
}

int Answer(long long S, long long T)
{
	int h1 = 0, h2 = 0;
	for(int i = 60; i >= 0; i--) if((S >> i)&1){
		h1 = i;
		break;
	}
	for(int i = 60; i >= 0; i--) if((T >> i)&1){
		h2 = i;
		break;
	}
	if(h1 == h2)
		return 2;
	if(h1 < h2){
		for(int i = 0; i < h1; i++) if(((S >> i)&1) != ((T >> i)&1))
			return 2;
		return 1;
	}
	for(int i = 0; i < h2; i++) if(((S >> i)&1) != ((T >> i)&1))
		return 2;
	return 0;
}

Compilation message

Encoder.cpp: In function 'void dfs_code(int, int, int)':
Encoder.cpp:44:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(done == adj[v].size() - 1 + (v == 0)){
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12328 KB Output is correct
2 Correct 6 ms 12340 KB Output is correct
3 Correct 7 ms 12508 KB Output is correct
4 Correct 7 ms 12340 KB Output is correct
5 Correct 7 ms 12316 KB Output is correct
6 Correct 7 ms 12340 KB Output is correct
7 Correct 7 ms 12404 KB Output is correct
8 Correct 7 ms 12344 KB Output is correct
9 Correct 7 ms 12404 KB Output is correct
10 Correct 7 ms 12312 KB Output is correct
11 Correct 7 ms 12380 KB Output is correct
12 Correct 7 ms 12400 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 20988 KB Output is correct - L = 50805
2 Correct 190 ms 20996 KB Output is correct - L = 267759
3 Correct 181 ms 21228 KB Output is correct - L = 21803
4 Correct 191 ms 21260 KB Output is correct - L = 1023
5 Partially correct 433 ms 49852 KB Output is partially correct - L = 2436747531
6 Partially correct 439 ms 49400 KB Output is partially correct - L = 1610678779
7 Partially correct 459 ms 49364 KB Output is partially correct - L = 1677623822
8 Correct 455 ms 49068 KB Output is correct - L = 262143
9 Incorrect 118 ms 31200 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -