Submission #733079

#	Time	Username	Problem	Language	Result	Execution time	Memory
733079		cig32	Snowy Roads (JOI16_snowy)	C++17	100 / 100	23 ms	1796 KiB

Anya

#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, bruh3[i-500]);
  }
}

Boris

#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.push_back(bruh1[i]);
    stob2.push_back(bruh2[i]);
  }
  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;
}

Compilation message (stderr)

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:56:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if(v1[i].size() < minsize) {
      |        ~~~~~~~~~~~~~^~~~~~~~~
Anya.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0; i<v1[id].size(); i++) {
      |                ~^~~~~~~~~~~~~~

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:51:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     if(v2[i].size() < minsize) {
      |        ~~~~~~~~~~~~~^~~~~~~~~
Boris.cpp: In function 'int Boris(int)':
Boris.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0; i<v2[id].size(); i++) {
      |                ~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45