제출 #1090739

#제출 시각아이디문제언어결과실행 시간메모리
1090739Tymond저장 (Saveit) (IOI10_saveit)C++17
0 / 100
154 ms10796 KiB
#include "grader.h" #include "encoder.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; const int MAXN = 1e3 + 7; const int MAXH = 40; int dist[MAXH][MAXN]; int rep[MAXN]; int parent[MAXN]; vi g[MAXN]; vi gt[MAXN]; int n, h, m; int Find(int a){ if(a == rep[a]){ return a; } return rep[a] = Find(rep[a]); } void Union(int a, int b){ rep[Find(a)] = Find(b); } void dfs(int v, int p){ parent[v] = p; for(auto u : g[v]){ if(u == p){ continue; } dfs(u, v); } } void countDist(int start){ dist[start][start] = 0; queue<int> q; q.push(start); while(sz(q)){ int v = q.front(); q.pop(); for(auto u : gt[v]){ if(u == start){ continue; } if(dist[start][u] == 0){ dist[start][u] = dist[start][v] + 1; q.push(u); } } } } void encode(int nv, int nh, int ne, int *v1, int *v2){ n = nv; h = nh; m = ne; for(int i = 0; i < n; i++){ rep[i] = i; } for(int i = 0; i < m; i++){ if(Find(v1[i]) != Find(v2[i])){ g[v1[i]].pb(v2[i]); g[v2[i]].pb(v1[i]); Union(v1[i], v2[i]); } gt[v1[i]].pb(v2[i]); gt[v2[i]].pb(v1[i]); } for(int i = 0; i < n; i++){ sort(all(g[i])); } dfs(0, 0); for(int i = 1; i < n; i++){ for(int y = 0; y < 10; y++){ if(parent[i] & (1 << y)){ encode_bit(1); }else{ encode_bit(0); } } } for(int i = 0; i < h; i++){ countDist(i); } for(int i = 0; i < h; i++){ queue<int> q; vi vis(n, 0); q.push(i); while(sz(q)){ int v = q.front(); q.pop(); vis[v] = 1; for(auto u : g[v]){ if(vis[u]){ continue; } if(dist[i][u] == dist[i][v]){ encode_bit(0); encode_bit(0); }else if(dist[i][u] == dist[i][v] + 1){ encode_bit(0); encode_bit(1); }else{ encode_bit(1); encode_bit(1); } q.push(u); } } } return; }
#include "grader.h" #include "decoder.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; const int MAXN = 1e3 + 7; const int MAXH = 40; int dist[MAXH][MAXN]; int parent[MAXN]; vi g[MAXN]; int n, h; void countDist(int start){ dist[start][start] = 0; queue<int> q; q.push(start); while(sz(q)){ int v = q.front(); q.pop(); for(auto u : g[v]){ if(u == start){ continue; } if(dist[start][u] == 0){ dist[start][u] = dist[start][v] + 1; q.push(u); } } } } void decode(int nv, int nh) { n = nv; h = nh; for(int i = 1; i < n; i++){ for(int y = 0; y < 10; y++){ if(decode_bit()){ parent[i] += (1 << y); } } g[i].pb(parent[i]); g[parent[i]].pb(i); } for(int i = 0; i < n; i++){ sort(all(g[i])); } for(int i = 0; i < h; i++){ countDist(i); } for(int i = 0; i < h; i++){ queue<int> q; vi vis(n, 0); q.push(i); while(sz(q)){ int v = q.front(); q.pop(); vis[v] = 1; for(auto u : g[v]){ if(vis[u]){ continue; } int x = decode_bit(); int y = decode_bit(); if(x == 0 && y == 0){ dist[i][u] = dist[i][v]; }else if(x == 0 && y == 1){ dist[i][u] = dist[i][v] + 1; }else{ dist[i][u] = dist[i][v] - 1; } q.push(u); } } } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...