Mai intai trebuie sa te autentifici.
Cod sursa(job #2018542)
Utilizator | Data | 5 septembrie 2017 12:44:21 | |
---|---|---|---|
Problema | Triplete | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.1 kb |
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#define NMAX 4096
int N;
vector<int> G[NMAX];
bool A[NMAX][NMAX];
int ntriangles;
void ReadInput() {
int M;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
A[x][y] = A[y][x] = 1;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Solve() {
for (int i = 0; i < N; ++i) sort(G[i].begin(), G[i].end(), greater<int>());
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
int niter = (G[i].size() < G[j].size()) ? i : j;
int nother = i ^ j ^ niter;
for (const int& x : G[niter]) {
if (x <= nother || x <= niter) break;
ntriangles += A[nother][x];
}
}
}
}
void WriteOutput() {
printf("%d\n", ntriangles);
}
int main() {
freopen("triplete.in", "r", stdin);
freopen("triplete.out", "w", stdout);
ReadInput();
Solve();
WriteOutput();
}