Submission #1210977

#TimeUsernameProblemLanguageResultExecution timeMemory
1210977Zbyszek99Saveit (IOI10_saveit)C++20
100 / 100
212 ms9404 KiB
#include "grader.h" #include "encoder.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vi graph[1001]; int P[1001]; bool odw[1001]; int dist[1001]; ll comb[1001]; void dfs_P(int v, int pop) { P[v] = pop; odw[v] = 1; forall(it,graph[v]) { if(odw[it] == 0) { dfs_P(it,v); } } } void bfs(int n, int start) { rep(i,n) odw[i] = 0; queue<pii> q; q.push({start,0}); while(!q.empty()) { pii t = q.front(); q.pop(); if(odw[t.ff]) continue; odw[t.ff] = 1; dist[t.ff] = t.ss; forall(it,graph[t.ff]) { q.push({it,t.ss+1}); } } } void encode(int n, int h, int e, int* v1, int* v2) { rep(i,e) { graph[v1[i]].pb(v2[i]); graph[v2[i]].pb(v1[i]); } dfs_P(0,0); rep(i,n) { rep(bit,10) { if(P[i] & (1 << bit)) encode_bit(1); else encode_bit(0); } } ll cur_pot = 1; rep(i,h) { bfs(n,i); rep(i,n) { if(P[i] == i) continue; if(dist[i] > dist[P[i]]) comb[i] += cur_pot; else if(dist[i] == dist[P[i]]) comb[i] += cur_pot*2; } cur_pot *= 3; } rep(i,n) { if(P[i] == i) continue; rep(bit,58) { if(comb[i] & (1LL << (ll)bit)) encode_bit(1); else encode_bit(0); } } }
#include "grader.h" #include "decoder.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; namespace { vi tree_[1001]; int P[1001]; ll comb[1001]; int type[1001][36]; void dfs_ans(int v, int pop, int start, int cur_d) { hops(start,v,cur_d); forall(it,tree_[v]) { if(it != pop) { if(P[v] == it) { if(type[v][start] == 0) dfs_ans(it,v,start,cur_d+1); else if(type[v][start] == 1) dfs_ans(it,v,start,cur_d-1); else dfs_ans(it,v,start,cur_d); } else { if(type[it][start] == 0) dfs_ans(it,v,start,cur_d-1); else if(type[it][start] == 1) dfs_ans(it,v,start,cur_d+1); else dfs_ans(it,v,start,cur_d); } } } } } void decode(int n, int h) { rep(i,n) { rep(bit,10) { int b = decode_bit(); P[i] += (1 << bit) * b; } if(P[i] != i) { tree_[P[i]].pb(i); tree_[i].pb(P[i]); } } rep(i,n) { if(P[i] == i) continue; rep(bit,58) { if(decode_bit() == 1) comb[i] += (1LL << (ll)bit); } rep(hh,h) { type[i][hh] = comb[i] % 3; comb[i] /= 3; } } rep(hh,h) { dfs_ans(hh,hh,hh,0); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...