Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
neske
1479 / 846 / 75
Регистрация: 26.03.2010
Сообщений: 2,904
#1

Сравнение скорости - C++

24.01.2012, 23:11. Просмотров 459. Ответов 6
Метки нет (Все метки)

вечер добрый.
смотрел задачи на codeforces, и заметил, что 90% решений на с++ написано в таком стиле, код взят случайный -

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
 
#define REP(AA,BB) for(int AA=0; AA<(BB); ++AA)
#define FOR(AA,BB,CC) for(int AA=(BB); AA<(CC); ++AA)
#define FC(AA,BB) for(__typeof((AA).begin()) BB=(AA).begin(); BB!=(AA).end(); ++BB)
#define SZ(AA) ((int)((AA).size()))
#define ALL(AA) (AA).begin(), (AA).end()
#define PB push_back
#define MP make_pair
 
using namespace std;
 
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
typedef long double LD;
 
struct edge {
        int v, w, g, s;
        int operator<(const edge &e) const {
                if(g==e.g)
                        return s<e.s;
                return g<e.g;
        }
};
 
int n, m, G, S, now=0;
edge E[50010];
vector<PII> ve[210]; PII par[210];
int vis[210];
 
int path(int a, int b) {
        memset(vis, 0, sizeof(int)*(n+1));
        vis[a]=1; queue<int> Q; Q.push(a);
        while(!Q.empty()) {
                int v=Q.front(); Q.pop();
                REP(i,SZ(ve[v])) {
                        int k=ve[v][i].first, e=ve[v][i].second;
                        if(!vis[k]) {
                                vis[k]=1;
                                par[k]=MP(v, e);
                                Q.push(k);
                        }
                }
        }
        return vis[b];
}
 
int del(int co) {
        int mx=-1, a=E[co].v, b=E[co].w;
        while(b!=a) {
                if(mx==-1 || E[par[b].second].s>E[mx].s)
                        mx=par[b].second;
                b=par[b].first;
        }
        if(E[mx].s<=E[co].s)
                return 0;
        int v=E[mx].v, w=E[mx].w;
        REP(i,SZ(ve[v])) {
                if(ve[v][i].second==mx) {
                        swap(ve[v][i],ve[v].back());
                        ve[v].pop_back();
                        break;
                }
        }
        REP(i,SZ(ve[w])) {
                if(ve[w][i].second==mx) {
                        swap(ve[w][i],ve[w].back());
                        ve[w].pop_back();
                        break;
                }
        }
        --now;
        return 1;
}
 
void add(int e) {
        ve[E[e].v].PB(MP(E[e].w, e));
        ve[E[e].w].PB(MP(E[e].v, e));
        ++now;
}
 
LL cost() {
        int gg=0, ss=0;
        REP(i,n) {
                REP(j,SZ(ve[i])) {
                        gg=max(gg, E[ve[i][j].second].g);
                        ss=max(ss, E[ve[i][j].second].s);
                }
        }
        return (LL)G*gg+(LL)S*ss;
}
 
int main(void) {
        scanf("%d%d%d%d", &n, &m, &G, &S);
        REP(i,m) {
                scanf("%d%d%d%d", &E[i].v, &E[i].w, &E[i].g, &E[i].s);
                --E[i].v; --E[i].w;
        }
        sort(E,E+m); LL res=-1;
        REP(i,m) {
                if(path(E[i].v, E[i].w)) {
                        if(del(i))
                                add(i);
                }
                else
                        add(i);
                if(now==n-1) {
                        if(res==-1)
                                res=cost();
                        else
                                res=min(res, cost());
                }
        }
        printf("%I64d\n", res);
        return 0;
}
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2012, 23:11     Сравнение скорости
Посмотрите здесь:

Сравнение скорости вычислений с# и С++ - C++
Сделал тестовые расчеты для сравнения скорости расчетов с# и С++ на примере умножения квадратных матриц. Сравнил расчеты без ускорения...

Сравнение скорости, условие или операция - C++
Подскажите, что быстрее сравнить 2 переменные if(x != y){ x = y + 1; } Или каждый раз расчитывать x = y + 1;

Сравнение скорости работы приложения vs 2010 и vs 2012 - C++
При умножении двух динамических матриц размера 1024х1024 чисел типа float, на CPU компилируя Visual Studio 2008 перемножение выполняется за...

Регулировка скорости - C++
Надо составить прогу, которая позволяет текст, содержащийся в файле, воспроизвести сигналами азбуки Морзе. При этом текст должен...

Программа замера скорости - C++
Здравствуйте. Мне нужно проанализировать скорость методов сортировки сортировки но почему то код не желает компилироваться. Рассмотрим...

Фикс скорости Игры - C++
Здравствуйте ув. программеры. Очень прошу помочь с подключением таймера для фиксирования скорости передвижения объектов в игре (пишу с...

Найти скорости движения пешехода - C++
Пешеход двигался в течение t1 минут с некоторой скоростью v1 и t2 минут с другой скоростью v2, которая в полтора раза больше v1. Найти...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rangerx
1932 / 1541 / 141
Регистрация: 31.05.2009
Сообщений: 2,911
25.01.2012, 00:11     Сравнение скорости #2
Цитата Сообщение от neske Посмотреть сообщение
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
Думаю скорость здесь ни при чём Макросы конечно могут использоваться как некий эквивалент inline функциям, но здесь, судя по всему, они используются просто для уменьшения веса исходника
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
25.01.2012, 00:15     Сравнение скорости #3
Цитата Сообщение от rangerx Посмотреть сообщение
просто для уменьшения веса исходника
интересно, какой вес оно считает, до препроцессорной обработки или после, если до, то считается ли сами директивы препроцессора или нет
neske
1479 / 846 / 75
Регистрация: 26.03.2010
Сообщений: 2,904
25.01.2012, 15:33  [ТС]     Сравнение скорости #4
ну ясно, спасибо)
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.01.2012, 15:41     Сравнение скорости #5
Никакого преимущества в скорости от вышеприведенных макросов не будет. Скорее они от лени написаны, чтобы писать меньше =\
Другое дело, когда вместо функций используют макросы, в таких случаях это делается для скорости.
neske
1479 / 846 / 75
Регистрация: 26.03.2010
Сообщений: 2,904
25.01.2012, 16:11  [ТС]     Сравнение скорости #6
А что на счет сишного варианта ввода / вывода?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 16:38     Сравнение скорости
Еще ссылки по теме:

Разница в скорости выполнения, итераторы - C++
Википедия for (ContainerType::iterator it = C.begin(),end = C.end(); it != end; ++it) { std::cout &lt;&lt; *it &lt;&lt; std::endl; } ...

вопрос по скорости ком порта - C++
есть оригинальная программа для обмена данными с сотовым телефоном. но версия моего аппарата не поддерживается. на основе команд с нее...

Результат запуска ракеты в зависимости от скорости - C++
Народ помогите пожалуста решить практическую работу, то я многого еще не понимаю. 1. Построить блок-схему, алгоритм и проверить...

Регулировка скорости вывода символа на экран - C++
Задача поставлена следующая - вывести на экран линию из символов, параметры которой задаются пользователем. В числе прочих есть параметр...

Разница в скорости выполнение программы C++ или C# - C++
И так здравствуйте,хотелось бы узнать почему в данном случае(то есть использование stl) c++ медленнее c# ,запускаю из релиза ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
25.01.2012, 16:38     Сравнение скорости #7
дело написано или нет?
Yandex
Объявления
25.01.2012, 16:38     Сравнение скорости
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru