oj.uz

Submission #558419

# Submission time Handle Problem Language Result Execution time Memory
558419 2022-05-07T09:42:40 Z fatemetmhr City (JOI17_city) C++17
8 / 100
 201 ms 16316 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 = 4e3 + 10;
const int maxnt = 4e5 + 10;

static ll code[maxn5], sz[maxn5], av[maxn5];
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);
	for(auto u : adj[v]) if(u != par){
		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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 652 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 1 ms 656 KB Output is correct
4 Correct 1 ms 656 KB Output is correct
5 Correct 1 ms 656 KB Output is correct
6 Correct 1 ms 660 KB Output is correct
7 Correct 1 ms 656 KB Output is correct
8 Correct 1 ms 656 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 1 ms 656 KB Output is correct
11 Correct 0 ms 656 KB Output is correct
12 Correct 1 ms 776 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 16124 KB Output is correct - L = 106485
2 Correct 178 ms 16136 KB Output is correct - L = 522223
3 Correct 201 ms 16208 KB Output is correct - L = 49223
4 Correct 177 ms 16316 KB Output is correct - L = 109227
5 Runtime error 56 ms 11980 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -