Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
neske
1503 / 870 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
#1

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

24.01.2012, 23:11. Просмотров 478. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сравнение скорости (C++):

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

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

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

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

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

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

6
rangerx
1935 / 1544 / 141
Регистрация: 31.05.2009
Сообщений: 2,913
25.01.2012, 00:11 #2
Цитата Сообщение от neske Посмотреть сообщение
почему смешивают все, зачем дефэйнов столко? дело в скорости, или что?
Думаю скорость здесь ни при чём Макросы конечно могут использоваться как некий эквивалент inline функциям, но здесь, судя по всему, они используются просто для уменьшения веса исходника
1
Jupiter
Каратель
Эксперт С++
6559 / 3980 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
25.01.2012, 00:15 #3
Цитата Сообщение от rangerx Посмотреть сообщение
просто для уменьшения веса исходника
интересно, какой вес оно считает, до препроцессорной обработки или после, если до, то считается ли сами директивы препроцессора или нет
1
neske
1503 / 870 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
25.01.2012, 15:33  [ТС] #4
ну ясно, спасибо)
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.01.2012, 15:41 #5
Никакого преимущества в скорости от вышеприведенных макросов не будет. Скорее они от лени написаны, чтобы писать меньше =\
Другое дело, когда вместо функций используют макросы, в таких случаях это делается для скорости.
1
neske
1503 / 870 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
25.01.2012, 16:11  [ТС] #6
А что на счет сишного варианта ввода / вывода?
0
AzaKendler
214 / 116 / 9
Регистрация: 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
Привет! Вот еще темы с ответами:

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

Оптимизация цикла по скорости - C++
Помогите пожалуйста оптимизировать данный цикл (изменить его, чтобы он выполнялся быстрее): int a = new int; int b = new int; ...

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

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


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

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

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