Submission #957591
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
struct UnionFind {
vector<int> data;
void init(int n) { data.assign(n, -1); }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if(x != y) {
if(data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) { return root(x) == root(y); }
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
int size(int x) { return -data[root(x)]; }
};
int main() {
int N; int E;
while(~scanf("%d%d", &N, &E)) {
UnionFind uf, uf3;
uf.init(N);
uf3.init(N * 3);
vector<int> outdeg(N, 0), indeg(N, 0);
vpii edges(E);
rep(i, E) {
int a; int b;
scanf("%d%d", &a, &b), -- a, -- b;
++ outdeg[a], ++ indeg[b];
edges[i] = { a, b };
uf.unionSet(a, b);
rep(k, 3)
uf3.unionSet(a * 3 + k, b * 3 + (k + 1) % 3);
}
sort(edges.begin(), edges.end());
edges.erase(unique(edges.begin(), edges.end()), edges.end());
vector<int> ccEdges(N, 0);
for(auto e : edges)
++ ccEdges[uf.root(e.first)];
vector<bool> hasP3(N);
rep(i, N) {
if(indeg[i] > 0 && outdeg[i] > 0)
hasP3[uf.root(i)] = true;
}
ll ans = 0;
rep(i, N) if(uf.root(i) == i) {
if(!hasP3[i])
ans += ccEdges[i];
}
vector<int> cc3Size(N * 3);
rep(i, N) if(hasP3[uf.root(i)]) {
rep(k, 3) if(uf3.findSet(i * 3, uf.root(i) * 3 + k))
++ cc3Size[uf.root(i) * 3 + k];
}
rep(i, N) if(uf.root(i) == i && hasP3[i]) {
if(uf3.findSet(i * 3 + 0, i * 3 + 1)) {
int n = cc3Size[i * 3 + 0];
ans += (ll)n * n;
} else {
rep(k, 3)
ans += (ll)cc3Size[i * 3 + k] * cc3Size[i * 3 + (k + 1) % 3];
}
}
printf("%lld\n", ans);
}
return 0;
}
Submission Info
Submission Time
2016-10-29 23:14:39+0900
Task
F - Blackout
User
anta
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
2308 Byte
Status
AC
Exec Time
45 ms
Memory
4992 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:37:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b), -- a, -- b;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1700 / 1700
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
3 ms
256 KB
0_01.txt
AC
2 ms
256 KB
0_02.txt
AC
2 ms
256 KB
1_00.txt
AC
2 ms
256 KB
1_01.txt
AC
8 ms
4096 KB
1_02.txt
AC
30 ms
4992 KB
1_03.txt
AC
31 ms
4992 KB
1_04.txt
AC
38 ms
4992 KB
1_05.txt
AC
38 ms
4992 KB
1_06.txt
AC
37 ms
4992 KB
1_07.txt
AC
31 ms
4992 KB
1_08.txt
AC
41 ms
4992 KB
1_09.txt
AC
31 ms
4992 KB
1_10.txt
AC
31 ms
4992 KB
1_11.txt
AC
31 ms
4992 KB
1_12.txt
AC
32 ms
4992 KB
1_13.txt
AC
37 ms
4992 KB
1_14.txt
AC
28 ms
4992 KB
1_15.txt
AC
27 ms
4992 KB
1_16.txt
AC
32 ms
4992 KB
1_17.txt
AC
21 ms
1024 KB
1_18.txt
AC
43 ms
4864 KB
1_19.txt
AC
43 ms
4864 KB
1_20.txt
AC
43 ms
4864 KB
1_21.txt
AC
43 ms
4992 KB
1_22.txt
AC
43 ms
4864 KB
1_23.txt
AC
45 ms
4864 KB
1_24.txt
AC
43 ms
4864 KB
1_25.txt
AC
43 ms
4992 KB
1_26.txt
AC
43 ms
4864 KB
1_27.txt
AC
43 ms
4864 KB
1_28.txt
AC
44 ms
4864 KB
1_29.txt
AC
43 ms
4864 KB
1_30.txt
AC
43 ms
4864 KB
1_31.txt
AC
43 ms
4864 KB
1_32.txt
AC
43 ms
4864 KB
1_33.txt
AC
43 ms
4992 KB
1_34.txt
AC
40 ms
3840 KB
1_35.txt
AC
36 ms
2688 KB
1_36.txt
AC
38 ms
3456 KB
1_37.txt
AC
42 ms
4480 KB
1_38.txt
AC
34 ms
2304 KB
1_39.txt
AC
33 ms
2048 KB
1_40.txt
AC
44 ms
4736 KB
1_41.txt
AC
42 ms
4608 KB
1_42.txt
AC
35 ms
3072 KB
1_43.txt
AC
36 ms
2688 KB
1_44.txt
AC
40 ms
3968 KB
1_45.txt
AC
33 ms
1792 KB
1_46.txt
AC
41 ms
4224 KB
1_47.txt
AC
42 ms
4608 KB
1_48.txt
AC
35 ms
2560 KB
1_49.txt
AC
37 ms
3200 KB