Submission #63027

ソースコード

?
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
// #define int long long
struct IoSetup {
IoSetup() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
}IoSetup;
using Int = __int128_t;
using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,-1,0,1,-1,1,-1,1};
inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T&b){if(a<b)return(a=b,1);return 0;}
template<class T>bool chmin(T &a, const T&b){if(b<a)return(a=b,1);return 0;}
template<typename T>
struct Edge {
int from, to;
T cost;
Edge(int to) : from(0), to(to), cost(T(1)) {}
Edge(int to, T cost) : from(0), to(to), cost(cost) {}
Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
const bool operator < (const Edge&e) const {
return (this->cost == e.cost ? (this->from == e.from ? this->to < e.to : this->from < e.from) : this->cost < e.cost);
}
};
template<typename T>
using Graph = vector<vector<Edge<T>>>;
template<typename T>
using Edges = vector<Edge<T>>;
template<typename G>
struct StringlyConnectedComponents {
const G &g; // 生グラフ
Graph<int> gg, rg;
vector<int> comp, order, used;
StringlyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
for(int i = 0; i < g.size(); i++) {
for(auto e:g[i]) {
gg[i].emplace_back((int)e.to);
rg[(int)e.to].emplace_back(i);
}
}
}
int operator[](int k) { // 頂点kが属する成分の番号を返す
return comp[k];
}
void dfs(int id) {
if(used[id]) return;
used[id] = true;
for(auto&e:gg[id]) dfs(e.to);
order.emplace_back(id); //帰りがけ順を記憶
}
void rdfs(int id, int cnt) { // 逆辺のグラフでDFSをし、cntでナンバリング
if(~comp[id]) return;
comp[id] = cnt;
for(auto&e:rg[id]) rdfs(e.to, cnt);
}
void build(Graph<int> &t) { // tには強連結成分ごとに縮約したグラフが格納される(多重辺が生える)
for(int i = 0; i < gg.size(); i++) dfs(i);
reverse(begin(order), end(order));
int ptr = 0;
for(int i : order) if(comp[i] == -1) rdfs(i, ptr++); // 帰りが遅かった頂点からDFS
t.resize(ptr);
for(int i = 0; i < g.size(); i++) {
for(auto&e:g[i]) {
int x = comp[i], y = comp[e.to];
if(x == y) continue;
t[x].emplace_back(y);
}
}
}
};
int in[11111], out[11111];
signed main() {
int n, m;
cin >> n >> m;
Graph<int> g(n);
for(int i = 0; i < m; i++) {
int s, t;
cin >> s >> t;
g[s].bash(t);
}
StringlyConnectedComponents<Graph<int>> scc(g);
Graph<int> sccg;
scc.build(sccg);
for(int i = 0; i < sccg.size(); i++) {
for(auto&&e:sccg[i]) {
in[i]++;
out[e.to]++;
}
}
int in0_cnt = 0, out0_cnt = 0;
for(int i = 0; i < sccg.size(); i++) {
in0_cnt += (in[i] == 0);
out0_cnt += (out[i] == 0);
}
if(sccg.size() == 1) in0_cnt = out0_cnt = 0;
cout << max(in0_cnt, out0_cnt) << endl;
return 0;
}

ステータス

項目 データ
問題 0964 - 道路網改修
ユーザー名 ei1821
投稿日時 2020-08-26 16:46:35
言語 C++14
状態 Accepted
得点 14
ソースコード長 3883 Byte
最大実行時間 51 ms
最大メモリ使用量 8992 KB

セット

セット 得点 Cases
1 ALL 14 / 14 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 32 ms 476 KB
1
in2.txt AC 24 ms 412 KB
1
in3.txt AC 21 ms 552 KB
1
in4.txt AC 21 ms 732 KB
1
in5.txt AC 15 ms 552 KB
1
in6.txt AC 21 ms 1660 KB
1
in7.txt AC 25 ms 3556 KB
1
in8.txt AC 25 ms 2056 KB
1
in9.txt AC 37 ms 6904 KB
1
in10.txt AC 38 ms 4136 KB
1
in11.txt AC 20 ms 2712 KB
1
in12.txt AC 27 ms 2804 KB
1
in13.txt AC 15 ms 464 KB
1
in14.txt AC 51 ms 7588 KB
1
in15.txt AC 45 ms 8992 KB
1
in16.txt AC 49 ms 7488 KB
1
in17.txt AC 46 ms 7520 KB
1
in18.txt AC 27 ms 648 KB
1
in19.txt AC 19 ms 596 KB
1
in20.txt AC 23 ms 2672 KB
1
in21.txt AC 15 ms 608 KB
1
in22.txt AC 24 ms 956 KB
1
in23.txt AC 27 ms 1440 KB
1
in24.txt AC 18 ms 1432 KB
1
in25.txt AC 22 ms 1716 KB
1
in26.txt AC 32 ms 2008 KB
1
in27.txt AC 21 ms 2556 KB
1
in28.txt AC 36 ms 3736 KB
1
in29.txt AC 34 ms 6248 KB
1
in30.txt AC 49 ms 7664 KB
1