| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 427173 |
2021-06-14T13:07:34 Z |
tqbfjotld |
City (JOI17_city) |
C++14 |
|
876 ms |
53612 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
int lch[500005];
int rch[500005];
int curnodes,n;
vector<int> adjl[250005];
int func(int node, int pa){
set<pair<int,int> > stuff;
for (auto x : adjl[node]){
if (x==pa) continue;
int res = func(x,node);
stuff.insert({res,x});
}
while (stuff.size()>2){
auto i1 = *stuff.begin();
stuff.erase(stuff.begin());
auto i2 = *stuff.begin();
stuff.erase(stuff.begin());
int nw = curnodes++;
lch[nw] = i2.second;
rch[nw] = i1.second;
stuff.insert({i2.first+1,nw});
}
if (stuff.size()==2){
auto i1 = *stuff.begin();
stuff.erase(stuff.begin());
auto i2 = *stuff.begin();
stuff.erase(stuff.begin());
lch[node] = i2.second;
rch[node] = i1.second;
return i2.first+1;
}
if (stuff.size()==1){
auto i1 = *stuff.begin();
lch[node] = i1.second;
return i1.first+1;
}
return 0;
}
void dfs2(int node, long long curamt, int pos){
//printf("ch of %d = %d %d\n",node,lch[node],rch[node]);
if (node<n){
// printf("code %d %lld\n",node,curamt+(1LL<<pos));
Code(node,curamt+(1LL<<pos));
}
if (lch[node]!=-1){
if (lch[node]<n) Code(lch[node],curamt+(5LL<<pos));
if (lch[lch[node]]!=-1){
dfs2(lch[lch[node]],curamt,pos+1);
}
if (rch[lch[node]]!=-1){
dfs2(rch[lch[node]],curamt+(1LL<<pos),pos+3);
}
}
if (rch[node]!=-1){
if (rch[node]<n) Code(rch[node],curamt+(7LL<<pos));
if (lch[rch[node]]!=-1){
dfs2(lch[rch[node]],curamt+(3LL<<pos),pos+3);
}
if (rch[rch[node]]!=-1){
dfs2(rch[rch[node]],curamt+(7LL<<pos),pos+3);
}
}
}
void Encode(int N, int A[], int B[])
{
n = N;
memset(lch,-1,sizeof(lch));
memset(rch,-1,sizeof(rch));
curnodes = N;
for (int x = 0; x<N-1; x++){
adjl[A[x]].push_back(B[x]);
adjl[B[x]].push_back(A[x]);
}
func(0,-1);
dfs2(0,0,0);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
string s1,s2;
for (int x = 0; x<64; x++){
if (S)s1.push_back((S&1)?'1':'0');
S>>=1;
if (T)s2.push_back((T&1)?'1':'0');
T>>=1;
}
s1.pop_back();
s2.pop_back();
for (int x = 0; x<min(s1.size(),s2.size());){
if (s1[x]=='0'){
if (s2[x]=='0') {
x++; continue;
}
if (s2[x+1]=='0'){
if (s2.size()==x+2){
return 0;
}
}
return 2;
}
else if (s2[x]=='0'){
if (s1[x+1]=='0'){
if (s1.size()==x+2){
return 1;
}
}
return 2;
}
else if (min(s1.size(),s2.size())==x+2){
if (s1[x]==s2[x] && s1[x+1]==s2[x+1]) {
x+=2;
continue;
}
else{
return 2;
}
}
else{
if (s1[x]==s2[x] && s1[x+1]==s2[x+1] && s1[x+2]==s2[x+2]){
x+=3;
continue;
}
return 2;
}
}
//printf("cmp %s %s\n",s1.c_str(),s2.c_str());
return s1.size()<s2.size()?1:0;
if (s1.size()<s2.size()){
for (int x = 0; x<s1.size(); x++){
if (s1[x]!=s2[x]) return 2;
}
return 1;
}
for (int x = 0; x<s2.size(); x++){
if (s1[x]!=s2[x]) return 2;
}
return 0;
}
Compilation message
Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
20 | for (int x = 0; x<min(s1.size(),s2.size());){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
Device.cpp:26:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
26 | if (s2.size()==x+2){
| ~~~~~~~~~^~~~~
Device.cpp:34:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | if (s1.size()==x+2){
| ~~~~~~~~~^~~~~
Device.cpp:40:42: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
40 | else if (min(s1.size(),s2.size())==x+2){
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
Device.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int x = 0; x<s1.size(); x++){
| ~^~~~~~~~~~
Device.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int x = 0; x<s2.size(); x++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
10444 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
8 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10368 KB |
Output is correct |
| 5 |
Correct |
7 ms |
10348 KB |
Output is correct |
| 6 |
Correct |
7 ms |
10328 KB |
Output is correct |
| 7 |
Correct |
6 ms |
10368 KB |
Output is correct |
| 8 |
Correct |
6 ms |
10400 KB |
Output is correct |
| 9 |
Correct |
7 ms |
10288 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10368 KB |
Output is correct |
| 11 |
Correct |
7 ms |
10364 KB |
Output is correct |
| 12 |
Correct |
7 ms |
10368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
283 ms |
18940 KB |
Output is correct - L = 373465 |
| 2 |
Correct |
276 ms |
18968 KB |
Output is correct - L = 176678 |
| 3 |
Correct |
258 ms |
18996 KB |
Output is correct - L = 177883 |
| 4 |
Correct |
258 ms |
18876 KB |
Output is correct - L = 32761 |
| 5 |
Partially correct |
671 ms |
41036 KB |
Output is partially correct - L = 124392879707 |
| 6 |
Partially correct |
673 ms |
41236 KB |
Output is partially correct - L = 63806742107 |
| 7 |
Partially correct |
754 ms |
41356 KB |
Output is partially correct - L = 127612431513 |
| 8 |
Correct |
647 ms |
40788 KB |
Output is correct - L = 134217727 |
| 9 |
Partially correct |
845 ms |
52308 KB |
Output is partially correct - L = 274877794560 |
| 10 |
Partially correct |
876 ms |
53508 KB |
Output is partially correct - L = 274877896960 |
| 11 |
Partially correct |
826 ms |
53612 KB |
Output is partially correct - L = 274877896960 |
| 12 |
Partially correct |
815 ms |
53540 KB |
Output is partially correct - L = 274877896960 |
| 13 |
Partially correct |
712 ms |
47240 KB |
Output is partially correct - L = 68719466752 |
| 14 |
Partially correct |
700 ms |
43584 KB |
Output is partially correct - L = 8589934080 |
| 15 |
Correct |
270 ms |
18872 KB |
Output is correct - L = 308953 |
| 16 |
Correct |
267 ms |
18944 KB |
Output is correct - L = 1348297 |
| 17 |
Correct |
271 ms |
18992 KB |
Output is correct - L = 234185 |
| 18 |
Partially correct |
784 ms |
46804 KB |
Output is partially correct - L = 68719364352 |
| 19 |
Partially correct |
765 ms |
46992 KB |
Output is partially correct - L = 68714678528 |
| 20 |
Partially correct |
869 ms |
47296 KB |
Output is partially correct - L = 68278999296 |
| 21 |
Partially correct |
735 ms |
45308 KB |
Output is partially correct - L = 68719474944 |
| 22 |
Partially correct |
741 ms |
45676 KB |
Output is partially correct - L = 94489279616 |
| 23 |
Partially correct |
776 ms |
43556 KB |
Output is partially correct - L = 94489279616 |
| 24 |
Partially correct |
695 ms |
44584 KB |
Output is partially correct - L = 103079210368 |
| 25 |
Partially correct |
725 ms |
42928 KB |
Output is partially correct - L = 103079188032 |
| 26 |
Partially correct |
768 ms |
43032 KB |
Output is partially correct - L = 103079196608 |
| 27 |
Partially correct |
797 ms |
42904 KB |
Output is partially correct - L = 206158356448 |
