| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 225969 |
2020-04-22T06:52:23 Z |
erd1 |
City (JOI17_city) |
C++14 |
|
448 ms |
9548 KB |
#include "Encoder.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)
out << (i == b?"":" ") << *i;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
return outIt(out << '[', all(v)) << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> v){
return out << "(" << v.first << ", " << v.second << ")";
}
pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }
vector<vector<int>> G;
vector<pii> mxch;
int haash(int i){
return i?haash(i>>4)^(i&15):0;
}
long long encode(vector<int> v){
vector<int> ans;
reverse(all(v));
int s = v.size();
if(!s)return 0;
//cout << v << " ";
while(v.size() && !v.back())v.pop_back();
while(v.size()){
if(v.back()){v.back() = haash(v.back())?haash(v.back()):1;
for(int i = __lg(v.back()); i >= 0; i--)ans.pb(v.back()>>i&1);
}
ans.pb(2);
v.pop_back();
}
for(int i = __lg(s); i >= 0; i--)ans.pb(s>>i&1);
//cout << ans << " ";
long long anss = 0;
for(auto i: ans)anss = anss*3+i;
//cout << anss << endl;
return anss;
}
vector<int> concat(vector<int> v, int i){
v.pb(i); return v;
}
void dfs(int i, int p, vector<int> v){
int cnt = 0;
if(mxch[i].ss)dfs(mxch[i].ss, i, concat(v, cnt++));
for(auto x: G[i])
if(x != p && x != mxch[i].ss)
dfs(x, i, concat(v, cnt++));
//cout << i << " ";
Code(i, encode(v));
//cout << "!" << endl;
}
pii dfs0(int i, int p){
for(auto x: G[i])if(x != p)dfs0(x, i);
mxch[p] = max(mxch[i]+1, mxch[p]);
}
void Encode(int N, int A[], int B[]) {
//cout << "inencode" << endl;
G.resize(N); mxch.resize(N);
for(int i = 0; i < N-1; i++)
G[A[i]].pb(B[i]), G[B[i]].pb(A[i]);
dfs0(0, 0);
//cout << "end1" << endl;
dfs(0, 0, vector<int>());
//cout << "end2" << endl;
}
#include "Device.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)
out << (i == b?"":" ") << *i;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
return outIt(out << '[', all(v)) << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> v){
return out << "(" << v.first << ", " << v.second << ")";
}
static pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }
void InitDevice()
{
}
static vector<int> decode(long long c){
vector<int> v, cs;
//cout << c << " ";
while(c)cs.pb(c%3), c/=3;
reverse(all(cs));
//cout << cs << " ";
int cur = 0;
for(auto i: cs){
if(i == 2)v.pb(cur), cur = 0;
else cur = cur*2+i;
}
reverse(all(v));
v.resize(cur, 0);
reverse(all(v));
//cout << v << endl;
return v;
}
int Answer(long long S, long long T) {
auto s = decode(S), t = decode(T); int a = 1;
//cout << S << s << endl << T << t << endl;
if(s.size() > t.size())swap(s, t), a = 1-a;
for(int i = 0; i < s.size(); i++)if(s[i] != t[i])return 2;
return a;
}
Compilation message
Encoder.cpp: In function 'pii dfs0(int, int)':
Encoder.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++)if(s[i] != t[i])return 2;
~~^~~~~~~~~~
Device.cpp: At global scope:
Device.cpp:27:12: warning: 'pii operator+(pii, int)' defined but not used [-Wunused-function]
static pii operator+(pii a, int b){ return {a.ff+b, a.ss}; }
^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1020 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1028 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1032 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1012 KB |
Output is correct |
| 8 |
Correct |
8 ms |
908 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1032 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1016 KB |
Output is correct |
| 11 |
Correct |
8 ms |
772 KB |
Output is correct |
| 12 |
Correct |
9 ms |
1032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
448 ms |
9548 KB |
Output isn't correct - L = 3615148028052 |
| 2 |
Halted |
0 ms |
0 KB |
- |
