oj.uz

Submission #486226

# Submission time Handle Problem Language Result Execution time Memory
486226 2021-11-11T02:49:23 Z kig9981 City (JOI17_city) C++17
8 / 100
 150 ms 15000 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
vector<int> adj[250000];
int node_cnt, W[250000], parent[250000], level[250000], F[250000], num[250000], R[250000];
 
long long compress(long long a, long long b, long long c) {return (a<<18)|(b<<9)|c;}
 
void dfs(int c)
{
	W[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		parent[n]=c;
		dfs(n);
		W[c]+=W[n];
	}
}
 
void dfs2(int c)
{
	num[c]=node_cnt++;
	for(auto n: adj[c]) if(level[n]==level[c] && parent[n]==c) {
		F[n]=F[c];
		dfs2(n);
	}
	R[c]=node_cnt-1;
}
 
void Encode(int N, int A[], int B[])
{
	priority_queue<pair<int,int>> Q;
	for(int i=0;i<N-1;i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	for(int i=0;i<N;i++) Q.emplace(W[i],i);
	for(int i=1;i<512 && Q.size();i++) {
		int c=Q.top().second;
		Q.pop();
		level[c]=1;
	}
	node_cnt=1; dfs2(0);
	for(int i=1;i<N;i++) if(level[parent[i]]!=level[i]) {
		F[i]=num[parent[i]];
		node_cnt=0; dfs2(i);
	}
	for(int i=0;i<N;i++) {
      assert(F[i]<512 && num[i]<512 && R[i]<512);
      Code(i,compress(F[i],num[i],R[i]));
    }
}
#include "Device.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
tuple<int,int,int> decompress(long long a) {return {(a>>18)&511,(a>>9)&511,a&511};}
 
void InitDevice() {}
 
int Answer(long long S, long long T)
{
	auto[sf,sl,sr]=decompress(S);
	auto[tf,tl,tr]=decompress(T);
	if(sf==tf) {
		if(tl<=sl && sr<=tr) return 0;
		if(sl<=tl && tr<=sr) return 1;
		return 2;
	}
	if(sf==0) {
		if(sl<=tf && tf<=sr) return 1;
	}
	if(tf==0) {
		if(tl<=sf && sf<=tr) return 0;
	}
	return 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6536 KB Output is correct
2 Correct 3 ms 6540 KB Output is correct
3 Correct 3 ms 6544 KB Output is correct
4 Correct 3 ms 6412 KB Output is correct
5 Correct 3 ms 6540 KB Output is correct
6 Correct 3 ms 6404 KB Output is correct
7 Correct 3 ms 6532 KB Output is correct
8 Correct 3 ms 6412 KB Output is correct
9 Correct 3 ms 6532 KB Output is correct
10 Correct 3 ms 6404 KB Output is correct
11 Correct 3 ms 6532 KB Output is correct
12 Correct 4 ms 6540 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 15000 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -