| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 733075 | cig32 | Snowy Roads (JOI16_snowy) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Anyalib.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
void Save(int place, int bit);
const int M = 10, MAXN = 500;
vector<int> v1[M];
vector<pair<int, int> > adj1[MAXN];
vector<int> stoa1, stob1;
int dep1[MAXN];
int ans1[MAXN];
int N_;
void InitAnya(int N, int *bruh1, int *bruh2) {
N_ = N;
for(int i=0; i<N-1; i++) {
stoa1.push_back(bruh1[i]);
stob1.push_back(bruh2[i]);
}
}
void dfs1(int node, int prv) {
dep1[node] = (prv == -1 ? 0 : dep1[prv] + 1);
if(prv != -1) v1[dep1[node] % M].push_back(node);
for(pair<int, int> x: adj1[node]) {
if(x.first != prv) {
ans1[x.first] = ans1[node] + x.second;
dfs1(x.first, node);
}
}
}
void Anya(int *bruh3) {
int N = N_;
for(int i=0; i<N; i++) {
adj1[i].clear();
}
for(int i=0; i<M; i++) {
v1[i].clear();
}
for(int i=0; i<N-1; i++) {
adj1[stoa1[i]].push_back({stob1[i], bruh3[i]});
adj1[stob1[i]].push_back({stoa1[i], bruh3[i]});
}
dfs1(0, -1);
int minsize = 1e9, id;
for(int i=0; i<M; i++) {
if(v1[i].size() < minsize) {
minsize = v1[i].size();
id = i;
}
}
for(int i=0; i<v1[id].size(); i++) {
for(int j=0; j<9; j++) {
int bruh = ans1[v1[id][i]] & (1 << j);
if(bruh > 0) bruh = 1;
Save(i * 9 + j, bruh);
}
}
for(int i=500; i<500+N-1; i++) {
Save(i, C[i-500]);
}
}
#include "Borislib.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int Ask(int place);
const int M = 10, MAXN = 500;
vector<int> v2[M];
vector<int> adj2[MAXN];
vector<int> stoa2, stob2;
int dep2[MAXN];
int par2[MAXN];
map<pair<int,int>,int> idedge;
void dfs2(int node, int prv) {
dep2[node] = (prv == -1 ? 0 : dep2[prv] + 1);
if(prv != -1) v2[dep2[node] % M].push_back(node);
par2[node] = prv;
for(int x: adj2[node]) {
if(x != prv) {
dfs2(x, node);
}
}
}
int minsize, id;
void InitBoris(int N, int *bruh1, int *bruh2) {
for(int i=0; i<N; i++) {
adj2[i].clear();
}
for(int i=0; i<M; i++) {
v2[i].clear();
}
idedge.clear();
for(int i=0; i<N-1; i++) {
idedge[{bruh1[i], bruh2[i]}] = idedge[{bruh2[i], bruh1[i]}] = i;
adj2[bruh1[i]].push_back(bruh2[i]);
adj2[bruh2[i]].push_back(bruh1[i]);
}
stoa2 = A;
stob2 = B;
dfs2(0, -1);
minsize = 1e9;
for(int i=0; i<M; i++) {
if(v2[i].size() < minsize) {
minsize = v2[i].size();
id = i;
}
}
}
int Boris(int city) {
int ans = 0;
while(dep2[city] % M != id) {
if(city == 0) return ans;
ans += Ask(500 + idedge[{city, par2[city]}]);
city = par2[city];
}
for(int i=0; i<v2[id].size(); i++) {
if(v2[id][i] == city) {
int add = 0;
for(int j=i*9+8; j>=i*9; j--) {
add = add * 2 + Ask(j);
}
ans += add;
}
}
return ans;
}