Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
#1

Сравнение скорости

24.01.2012, 23:11. Просмотров 513. Ответов 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;
}
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2012, 23:11
Ответы с готовыми решениями:

Сравнение скорости вычислений с# и С++
Сделал тестовые расчеты для сравнения скорости расчетов с# и С++ на примере...

Сравнение величин измерения скорости
Написать программу которая должна запросить введение переменных, одна из них...

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

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

Сравнение текста из файла и сравнение с текстом в программе char - Dev C++
Доброго времени суток! Имеется код программы: ifstream test(&quot;primer.txt&quot;);...

6
rangerx
1941 / 1550 / 478
Регистрация: 31.05.2009
Сообщений: 2,913
25.01.2012, 00:11 #2
Цитата Сообщение от neske Посмотреть сообщение
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
Думаю скорость здесь ни при чём Макросы конечно могут использоваться как некий эквивалент inline функциям, но здесь, судя по всему, они используются просто для уменьшения веса исходника
1
Jupiter
Каратель
Эксперт С++
6568 / 3989 / 400
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
25.01.2012, 00:15 #3
Цитата Сообщение от rangerx Посмотреть сообщение
просто для уменьшения веса исходника
интересно, какой вес оно считает, до препроцессорной обработки или после, если до, то считается ли сами директивы препроцессора или нет
1
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
25.01.2012, 15:33  [ТС] #4
ну ясно, спасибо)
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.01.2012, 15:41 #5
Никакого преимущества в скорости от вышеприведенных макросов не будет. Скорее они от лени написаны, чтобы писать меньше =\
Другое дело, когда вместо функций используют макросы, в таких случаях это делается для скорости.
1
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
25.01.2012, 16:11  [ТС] #6
А что на счет сишного варианта ввода / вывода?
0
AzaKendler
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
25.01.2012, 16:38 #7
дело написано или нет?
0
25.01.2012, 16:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2012, 16:38

Регулировка скорости
Надо составить прогу, которая позволяет текст, содержащийся в файле,...

Оптимизация цикла по скорости
Помогите пожалуйста оптимизировать данный цикл (изменить его, чтобы он...

Фикс скорости Игры
Здравствуйте ув. программеры. Очень прошу помочь с подключением таймера для...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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