Не давно я наткнулся на эту задачу И уже довольно долгое время ломаю голову, почему и где программка зацикливается. Я надеюсь, вы — как опытные гуру, сможете мне помочь...
#include <fstream>
#include <string.h>
#include<string>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include<cstdio>
#include<vector>
#include <string>
using namespace std;
int cat[1000]={0}; bool color[5000]={0};
int a[5000][5000]={0},n,k,c=0;
int dfs(int i)
{
bool f=true;
color[i]=1;
if (cat[i]<=k)
{for (int j=1;j<=n;j++)
{
if (color[j]==0&&a[i][j]==1)
{ f=false;if (cat[j]!=0) cat[j]+=cat[i];dfs(j);}}
if (f) c++;}
return 0;
}
int main()
{
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>cat[i];
for (int j=1; j<n;j++)
{int x,y; cin>>x>>y; a[x][y]=1;a[y][x]=1;}
dfs(1);
cout<<c;
return 0;
}
Заранее спасибо)
N — до 105, а у тебя объявлена матрица смежности до 5000. При попытки перейти в вершину с индексом больше 5000, программа обращается в неизвестную область памяти, и происходит непонятно что.
В тесте, который не проходит, размер входит в диапазон...
Позвольте для начала разнести некоторые вещи из вашего кода в пух и прах. Цель — рассказать, почему какие-то вещи делать не надо и как надо делать вместо этого.
cat[i] <= k
, причём сначала идёт цикл по всем вершинам, удовлетворяющим какому-то условию, а потом как-то модифицируется некоторая переменнаяc
. Таким образом человек, не знающий решения задачи и хода ваших мыслей, может его хотя бы попробовать восстановить.void
, который можно указывать, когда функция ничего не возвращает. Например:void dfs(int i)
. Тогда возврат из середины функции пишется просто командойreturn;
, а в конце функции можно вообщеreturn;
не ставить — он сам поставится. С функциейmain
так нельзя — она особенная и должна возвращатьint
. Опять же, ради повышения читаемости: если я вижу, чтоdfs
возвращает некоторое значение, то я предполагаю, что оно где-то используется и очень удивляюсь, когда вижуreturn 0;
и то, что результат вызововdfs(1)
иdfs(j)
никак не используется.int
,double
) и массивы из них в C++ по умолчанию инициализириются нулями (в отличие от локальных, в которых может быть любая фигня и поэтому надо инициализировать явно:int x = 0
). Поэтому, в частности, вам необязательно их инициализировать нулями. Более того, конструкцияint a[10] = { x }
вовсе не заполняет массив иксами, как может показаться на первый взгляд — пример. Происходит что-то менее очевидное: все указанные в скобках элементы заполняются указанными значениями, а остальные — значениями по умолчанию. Записьint a[10] = { 0 }
притворяется, будто бы она обозначает "заполни всё нулями", хотя это не так, поэтому так писать не стоит. Если у вас глобальный массив — оставьте его вообще без инициализации, он будет заполнен нулями. Если локальный (или хотите явно проинициализировать глобальный массив) — напишитеint a[10] = {}
— в этом случае все элементы точно заполнятся значениями по умолчанию.MAX_N
илиMAX_VERTICES
) и используете её. При этом не стоит использовать одну константу для разных по смыслу вещей: если у вас 1000 вершин и 1000 рёбер (и вы хотите хранить рёбра в списке), заведите разные константы: возможно, вы вспомните, что на самом деле вам надо хранить каждое ребро дважды (в одну сторону и в другую) или нужно добавлять дополнительные рёбра в граф. Например:Собственно, последняя рекомендация оказалась бы для вас спасительной: у вас размер массива
cat
не такой, как для остальных (14763809).Большое спасибо за подробное объяснение!=) Выручил!
на самом деле можно — по стандартам C99 и C++11 отсутствие
return
в main (и только в main) интерпретируется какreturn 0;
Во избежание недопонимания хочу уточнить:
main
всё равно обязана возвращатьint
, просто (в отличие от любой другой функции) у неё в конце как будто дописана строчкаreturn 0;
.И ещё, применительно именно к олимпиадному программированию: к моему великому сожалению, до сих пор во многих соревнованиях используется не C11 и даже не C99, а старый как мир C89, а в нём этого правила про подразумевающийся
return 0
нет, а и его надо писать самостоятельно.Небольшие дополнения к тому, что сказал Егор:
0) Если ты научишься оформлять свой код в "хороший" стиль — то спустя какое-то время ты начнешь писать с меньшим количеством багов, ты сам свой код будешь намного легче читать. Более того, как это ни странно, скорость написания кода со временем даже повысится, потому что ты, продумывая очередную строчку, будешь намного лучше ориентироваться в том, что написал выше. К тому же, стандартные алгоритмы будут запоминаться очень быстро, буквально после нескольких сданных задач.
1) Почему ты все действия делаешь в одной строке? Опять-таки, в "хорошем" стиле одна точка с запятой — одна строка. Если действия делаются через запятую — то можно располагать их в одной строке. Не экономь строчки, ты осложняешь себе чтение кода. Лучше уж сделай разрешение на своем компьютере чуть поменьше или удали все лишние окна из своего компилятора.
Так же между различными смысловыми частями кода(например, между различными функциями) лучше оставлять дополнительный перенос строки. Например:
2) В правилах "хорошего тона" есть еще один момент: битовые и логические операции стоит делать без пробела, остальные — с пробелом.
Впрочем, мне говорят, что далеко не всегда и не везде так делают.
3) Очень желательно, чтобы типы переменных соответствовали тому, как ты используешь. К примеру, насколько я вижу, свою матрицу a ты используешь как bool, а она при этом имеет тип int. Не надо так делать.
4) Желательно ставить свои константы с некоторым запасом. Делается это так:
где 5000 — это то число, которое указано в условии задачи, а 13 — это тот запас, который ты оставляешь.
Иногда тебе в задачах требуется для некоторых массивов увеличить константу в несколько раз. Делать это можно двумя способами
а)
он очень плохой, но если у тебя размеры всех массивов 4 * 5000 — то почему бы и нет?
б)
этот способ более предпочтителен
P.S. Разумеется, все вышеперечисленные правила не "железные" и ты, когда начнешь ими пользоваться, для себя выделишь некоторые исключения. Но в большинстве своем эти правила лучше соблюдать — тогда код будет получаться чистым и писаться будет буквально сам, очень быстро.
Удали свой пункт (2), пока никто не видел. В нем написана полная чушь.
Соглашусь с пунктами 0, 1, 3.
С пунктом 2 не соглашусь — он разный в разных code style. Я практически нигде не видел рекомендацию "не отделяйте бинарные операции пробелами", как раз везде пишут наоборот (в том же Google Code Style). Кстати, тернарные операции — это операции с трёмя аргументами (а такая ровно одна —
cond ? res_true : res_false
). Полагаю, имелись в виду битовые и логические.С пунктом 4 категорически не соглашусь — "делать константы с запасом" есть хак, подобный "а давайте добавим случайную +1 в формулу, авось пройдёт" — сдать задачу может помочь, но я считаю, что в процессе обучения и изучения алгоритмов, а также на работе так делать нельзя. Если автор не понимает, как работает программа, то что-то не так, а если понимает — то должен и понимать, нужен ли запас, и если да — какой точно. Например, если длина строки во входе равна 100, то нужен массив размером ровно 101 — плюс один символ на null terminator. Если я при этом читаю при помощи
fgets
, то нужен массив размером 103 — один символ на null terminator и два символа на перевод строки в Windows. Особенно эти ошибки ± 1 любят возникать в каких-то динамиках и тому подобному. В процессе обучения, мне кажется, очень важно думать и полностью понимать происходящее.Рекомендацию "а" из пункта 4 я считаю вредной — вводится константа с неверным именем —
MAX_N
не равен 5·4000, так что константа не только не помогает, но и вредит при чтении кода — начинает казаться, что на самом деле n ≤ 10 000 и возникает закономерный вопрос: а где, собственно, требуемый решению четырёхкратный запас? Разумным считаю вариант "б", где размеры массивов вычисляются из констант на месте. Если какая-то константа часто возникает (например,3 * MAX_N
), возможно, стоит её вынести под каким-то названием вроде "размер массива с запасом для динамики" или "размер для массива с зацикленной строчкой" (скажем,CYCLED_STR_ARR_SIZE = 3 * MAX_N + 1
).На контестах некоторые, к сожалению, любят делать запас в сотню-другую элемнентов и аргументируют это "по-другому не заходит" вместо того, чтобы понять, почему именно нужен запас в данном конкретном случае. Иногда такие запасы маскируют выход за границы массивов, а в сочетании со статическими массивами фиксированного такие ошибки становится невозможно отловить на маленьких тестах — просто потому что массива хватает. Поэтому я везде, где могу, выделяю вектора размера в точности такого размера, как мне надо, без запасов. Если я ошибся на десять — это примерно с одинаковой вероятностью будет бред и на большом тесте, и на маленьком.
Я немного подправил то, что выше. Конечно, имелись ввиду битовые операции и логические, с утра такая каша в голове иногда бывает :) . Спасибо за замечания. Однако...
По поводу пункта 2 — я где-то в свое время услышал/увидел такой стиль кода, где именно — сейчас уже не помню. Сам я в то время не обращал внимания на стиль написания кода(как и автор нынешнего топика), однако перестроил свой код именно под стиль "между некоторыми операциями лучше ставить пробел, между некоторыми — нет". И выступая в составах различных команд СГУ, наблюдая за различными кодерами в моей команде, я пришел к выводу, что все это правило используют. Операции, которые разделяются пробелом/не разделяются, различались у всех, однако у всех класс "беспробельных" случаев не был пустым.
Пункт 4. Позволь мне, в свою очередь, не согласиться с тобой :) . Моя идея — давайте будем использовать один и тот же аппарат что для оценки времени, что для оценки памяти. А именно — давайте что для первого, что для второго случая будем считать асимптотику и константу у этой асимптотики. Так мы гораздо быстрее изучим аппарат асимптотических оценок. И не только сам аппарат, но и "частные случаи", когда нужно чуть внимательнее считать оценку.
Разумеется, оценка памяти нужна гораздо более тщательная. Однако, раз она нужна более тщательная — значит, мы еще быстрее сможем изучить аппарат :) .