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

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

Восстановить пароль Регистрация
 
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
24.01.2012, 23:11     Сравнение скорости #1
вечер добрый.
смотрел задачи на 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++
Проверка скорости работы своего list C++
C++ Фикс скорости Игры
Программа замера скорости C++
C++ разница в скорости выполнения, итератры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
25.01.2012, 00:11     Сравнение скорости #2
Цитата Сообщение от neske Посмотреть сообщение
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
Думаю скорость здесь ни при чём Макросы конечно могут использоваться как некий эквивалент inline функциям, но здесь, судя по всему, они используются просто для уменьшения веса исходника
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
25.01.2012, 00:15     Сравнение скорости #3
Цитата Сообщение от rangerx Посмотреть сообщение
просто для уменьшения веса исходника
интересно, какой вес оно считает, до препроцессорной обработки или после, если до, то считается ли сами директивы препроцессора или нет
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
25.01.2012, 15:33  [ТС]     Сравнение скорости #4
ну ясно, спасибо)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.01.2012, 15:41     Сравнение скорости #5
Никакого преимущества в скорости от вышеприведенных макросов не будет. Скорее они от лени написаны, чтобы писать меньше =\
Другое дело, когда вместо функций используют макросы, в таких случаях это делается для скорости.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
25.01.2012, 16:11  [ТС]     Сравнение скорости #6
А что на счет сишного варианта ввода / вывода?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 16:38     Сравнение скорости
Еще ссылки по теме:

Сравнение скорости работы приложения vs 2010 и vs 2012 C++
Сравнение скорости, условие или операция C++
Регулировка скорости C++

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

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

Текущее время: 07:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru