CodeChef-BEARS : Bears and Bees
問題概要
G=(V,E)からG'を以下のように得る。G'=(V',E')とすると、V'=Eで、辺aと辺bがGで同じ頂点に接続していたら(a,b) in E'となる。今、グラフG[0]=(V,E)(|V|, |E|<1000)がある。G[0]を変換してG[1]を得る。G[1]を変換してG[2]を得る。G[2]を変換してG[3]を得る。G[3]の頂点数と辺数を求める問題。
解法
まず、|E|<1000なのでG[1]は陽に持てる(らしいけど実際は定数倍でTLEした)。次に、G[2]の次数列を計算する。G[2]の次数列が計算できたらG[3]の頂点数が分かる(次数列の和の半分)。また、G[3]の次数列そのものは分からなくてもG[3]の次数列の和はsum d[i]*(d[i]-1)で求めることができるので、G[3]の頂点数はG[3]の次数列の和の半分となる。
acceptされたコード
計算量O(M^2)。
#include <cstdio> #include <vector> #include <cstring> using namespace std; const int MAX_N = 1000; const int MAX_M = 1000; const int MAX_L = 500000; int N0, M0; vector<int> g0[MAX_N]; pair<int,int> p0[MAX_M]; vector<int> g1[MAX_M]; int gg1[MAX_M]; pair<int,int> p1[MAX_L]; int to_idx[MAX_N][MAX_N]; bool visited[MAX_N][MAX_N]; int deg2[MAX_L]; void init(){ scanf("%d%d",&N0, &M0); memset(to_idx, 0, sizeof(to_idx)); memset(deg2, 0, sizeof(deg2)); memset(gg1, 0, sizeof(gg1)); memset(visited, false, sizeof(visited)); for(int i=0; i<N0; i++){ g0[i].clear(); } for(int i=0; i<M0; i++){ int x, y; scanf("%d%d", &x, &y); x--; y--; g0[x].push_back(y); g0[y].push_back(x); p0[i] = make_pair(x, y); to_idx[x][y] = to_idx[y][x] = i; } } void solve(){ int N1 = M0, M1 = 0, pp = 0; for(int i=0; i<N1; i++){ int x = p0[i].first, y = p0[i].second; for(int j=0; j<(int)g0[x].size(); j++){ if(g0[x][j]!=y){ gg1[i]++; M1++; if(to_idx[x][g0[x][j]] > i && !visited[i][to_idx[x][g0[x][j]]]){ visited[i][to_idx[x][g0[x][j]]] = true; p1[pp++] = make_pair(i, to_idx[x][g0[x][j]]); } } } for(int j=0; j<(int)g0[y].size(); j++){ if(g0[y][j]!=x){ gg1[i]++; M1++; if(to_idx[y][g0[y][j]] > i && !visited[i][to_idx[y][g0[y][j]]]){ visited[i][to_idx[y][g0[y][j]]] = true; p1[pp++] = make_pair(i, to_idx[y][g0[y][j]]); } } } } M1 /= 2; int N2 = M1, M2 = 0; for(int i=0; i<N2; i++){ int x = p1[i].first, y = p1[i].second; deg2[i] += gg1[x]+gg1[y]-2; M2 += deg2[i]; } M2 /= 2; long long ans = 0; for(int i=0; i<N2; i++){ ans += (long long)deg2[i]*(deg2[i]-1); } printf("%d %lld\n", M2, ans/2); } int main(){ int T; scanf("%d", &T); for(;T--;){ init(); solve(); } return 0; }