# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
427071 |
2021-06-14T12:09:33 Z |
tqbfjotld |
City (JOI17_city) |
C++14 |
|
274 ms |
48632 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> chlist[250005];
int curnodes,n;
vector<int> adjl[250005];
const int numch = 3;
long long expp[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()>numch){
int nw = curnodes++;
int mxv = -1;
for (int x = 0; x<numch; x++){
auto i = *stuff.begin();
stuff.erase(stuff.begin());
chlist[nw].push_back(i.second);
mxv = i.first;
}
stuff.insert({mxv+1,nw});
}
int mxv = -1;
for (auto x : stuff){
mxv = x.first;
chlist[node].push_back(x.second);
}
return mxv+1;
}
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+expp[pos]-1LL);
}
for (long long x = 0; x<chlist[node].size(); x++){
dfs2(chlist[node][x],curamt+x*expp[pos],pos+1);
}
}
void Encode(int N, int A[], int B[])
{
n = N;
expp[0] = 1;
for (int x = 1; x<64; x++){
expp[x] = expp[x-1]*numch;
}
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;
const int numch = 3;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
S++; T++;
string s1,s2;
for (int x = 0; x<64; x++){
if (S){
s1.push_back('0'+S%numch);
}
S/=numch;
if (T){
s2.push_back('0'+T%numch);
}
T/=numch;
}
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
Encoder.cpp: In function 'void dfs2(int, long long int, int)':
Encoder.cpp:43:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (long long x = 0; x<chlist[node].size(); x++){
| ~^~~~~~~~~~~~~~~~~~~~
Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int x = 0; x<s1.size(); x++){
| ~^~~~~~~~~~
Device.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int x = 0; x<s2.size(); x++){
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12296 KB |
Output is correct |
2 |
Correct |
9 ms |
12296 KB |
Output is correct |
3 |
Correct |
8 ms |
12372 KB |
Output is correct |
4 |
Correct |
7 ms |
12292 KB |
Output is correct |
5 |
Correct |
7 ms |
12272 KB |
Output is correct |
6 |
Correct |
9 ms |
12192 KB |
Output is correct |
7 |
Correct |
8 ms |
12380 KB |
Output is correct |
8 |
Correct |
8 ms |
12296 KB |
Output is correct |
9 |
Correct |
9 ms |
12372 KB |
Output is correct |
10 |
Correct |
8 ms |
12296 KB |
Output is correct |
11 |
Correct |
8 ms |
12304 KB |
Output is correct |
12 |
Correct |
8 ms |
12292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
21024 KB |
Output is correct - L = 894704 |
2 |
Correct |
274 ms |
20996 KB |
Output is correct - L = 43188520 |
3 |
Correct |
270 ms |
20892 KB |
Output is correct - L = 583836 |
4 |
Correct |
261 ms |
20944 KB |
Output is correct - L = 29523 |
5 |
Runtime error |
177 ms |
48632 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |