# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
427003 |
2021-06-14T11:44:25 Z |
tqbfjotld |
City (JOI17_city) |
C++14 |
|
929 ms |
65268 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] = i1.second;
rch[nw] = i2.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] = i1.second;
rch[node] = i2.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){
dfs2(lch[node],curamt,pos+1);
}
if (rch[node]!=-1){
dfs2(rch[node],curamt+(1LL<<pos),pos+1);
}
}
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();
//printf("cmp %s %s\n",s1.c_str(),s2.c_str());
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:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int x = 0; x<s1.size(); x++){
| ~^~~~~~~~~~
Device.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int x = 0; x<s2.size(); x++){
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10372 KB |
Output is correct |
2 |
Correct |
7 ms |
10372 KB |
Output is correct |
3 |
Correct |
8 ms |
10328 KB |
Output is correct |
4 |
Correct |
7 ms |
10384 KB |
Output is correct |
5 |
Correct |
7 ms |
10384 KB |
Output is correct |
6 |
Correct |
8 ms |
10312 KB |
Output is correct |
7 |
Correct |
7 ms |
10348 KB |
Output is correct |
8 |
Correct |
6 ms |
10344 KB |
Output is correct |
9 |
Correct |
7 ms |
10372 KB |
Output is correct |
10 |
Correct |
6 ms |
10372 KB |
Output is correct |
11 |
Correct |
6 ms |
10372 KB |
Output is correct |
12 |
Correct |
8 ms |
10372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
24700 KB |
Output is correct - L = 16383 |
2 |
Correct |
294 ms |
24744 KB |
Output is correct - L = 114431 |
3 |
Correct |
307 ms |
24740 KB |
Output is correct - L = 16383 |
4 |
Correct |
273 ms |
24852 KB |
Output is correct - L = 1023 |
5 |
Correct |
682 ms |
53060 KB |
Output is correct - L = 134217578 |
6 |
Correct |
672 ms |
52668 KB |
Output is correct - L = 134217727 |
7 |
Correct |
721 ms |
52552 KB |
Output is correct - L = 134217663 |
8 |
Correct |
763 ms |
52344 KB |
Output is correct - L = 262143 |
9 |
Partially correct |
831 ms |
64184 KB |
Output is partially correct - L = 68719476735 |
10 |
Partially correct |
838 ms |
65024 KB |
Output is partially correct - L = 68719476733 |
11 |
Partially correct |
929 ms |
65268 KB |
Output is partially correct - L = 68719476223 |
12 |
Partially correct |
893 ms |
65180 KB |
Output is partially correct - L = 68719473471 |
13 |
Partially correct |
840 ms |
58944 KB |
Output is partially correct - L = 34359738367 |
14 |
Partially correct |
730 ms |
55080 KB |
Output is partially correct - L = 17179869183 |
15 |
Correct |
266 ms |
24864 KB |
Output is correct - L = 32767 |
16 |
Correct |
276 ms |
24924 KB |
Output is correct - L = 131071 |
17 |
Correct |
264 ms |
24968 KB |
Output is correct - L = 32255 |
18 |
Partially correct |
754 ms |
58316 KB |
Output is partially correct - L = 34359400255 |
19 |
Partially correct |
777 ms |
58732 KB |
Output is partially correct - L = 34358108160 |
20 |
Partially correct |
729 ms |
58444 KB |
Output is partially correct - L = 34294005760 |
21 |
Partially correct |
736 ms |
56760 KB |
Output is partially correct - L = 34359672831 |
22 |
Partially correct |
820 ms |
57492 KB |
Output is partially correct - L = 34358460416 |
23 |
Partially correct |
706 ms |
55308 KB |
Output is partially correct - L = 34358460416 |
24 |
Partially correct |
694 ms |
56420 KB |
Output is partially correct - L = 17175969792 |
25 |
Partially correct |
696 ms |
54416 KB |
Output is partially correct - L = 17172496384 |
26 |
Partially correct |
669 ms |
54444 KB |
Output is partially correct - L = 8588656640 |
27 |
Partially correct |
675 ms |
54232 KB |
Output is partially correct - L = 4292378624 |