Submission #00186

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
class bipartite_matching{
private:
int V;
vector< vector< int > > info;
vector< int > match;
vector< bool > used;
public:
bipartite_matching(int V_size):V(V_size){
info.resize(V_size);
used.resize(V_size);
match.resize(V_size);
};
void add_edge( int u, int v){
info[u].push_back(v);
info[v].push_back(u);
}
bool dfs( int v){
used[v] = true;
for(int i = 0; i < info[v].size(); i++){
int u = info[v][i], w = match[u];
if(w < 0 || !used[w] && dfs(w)){
match[v] = u, match[u] = v;
return true;
}
}
return false;
}
int run(){
match.assign(V,-1);
int ret = 0;
for(int i = 0; i < V; i++){
if(match[i] < 0){
used.assign(V,false);
if(dfs(i)) ret++;
}
}
return ret;
}
};
vector< int > edge[1005];
int main()
{
int rx[3], ry[3];
int m, n, px[1000], py[1000], s[1000], t[1000];
cin >> m;
for(int i = 0; i < m; i++) {
cin >> rx[i] >> ry[i];
}
cin >> n;
bipartite_matching bp(n + m);
for(int i = 0; i < n; i++) {
cin >> px[i] >> py[i] >> s[i] >> t[i];
}
int S[3] = {n, n + 1, n + 2};
for(int i = 0; i < m; i++) {
for(int j = i + 2; j < m; j++) {
int dist2 = (int)(pow(rx[j] - px[i], 2.0) + pow(ry[j] - py[i], 2.0));
if(dist2 <= pow(s[j] - t[i], 2.0)) {
bp.add_edge(i, j);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
int dist2 = (int)(pow(rx[j] - px[i], 2.0) + pow(ry[j] - py[i], 2.0));
if(dist2 <= pow(t[i], 2.0)) {
bp.add_edge(S[j], i);
}
}
}
puts(bp.run() - m >= 0 ? "YES" : "NO");
}

ステータス

項目 データ
問題 0009 - ラボライブ　タフグローバルフェスティバル
ユーザー名 I dont any
投稿日時 2015-08-28 11:59:09
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 1785 Byte
最大実行時間 27 ms
最大メモリ使用量 864 KB

セット

セット 得点 Cases
1 ALL 0 / 40 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
scrambled_00.txt AC 19 ms 476 KB
1
scrambled_01.txt AC 18 ms 672 KB
1
scrambled_02.txt AC 21 ms 740 KB
1
scrambled_03.txt WA 21 ms 800 KB
1
scrambled_04.txt AC 21 ms 672 KB
1
scrambled_05.txt AC 22 ms 676 KB
1
scrambled_06.txt WA 22 ms 680 KB
1
scrambled_07.txt AC 21 ms 684 KB
1
scrambled_08.txt AC 21 ms 680 KB
1
scrambled_09.txt AC 21 ms 492 KB
1
scrambled_10.txt WA 26 ms 556 KB
1
scrambled_11.txt AC 20 ms 628 KB
1
scrambled_12.txt AC 21 ms 564 KB
1
scrambled_13.txt WA 24 ms 640 KB
1
scrambled_14.txt AC 17 ms 832 KB
1
scrambled_15.txt WA 24 ms 640 KB
1
scrambled_16.txt WA 21 ms 704 KB
1
scrambled_17.txt WA 24 ms 652 KB
1
scrambled_18.txt WA 18 ms 716 KB
1
scrambled_19.txt WA 13 ms 648 KB
1
scrambled_20.txt WA 16 ms 456 KB
1
scrambled_21.txt WA 16 ms 640 KB
1
scrambled_22.txt WA 19 ms 704 KB
1
scrambled_23.txt WA 17 ms 768 KB
1
scrambled_24.txt WA 23 ms 668 KB
1
scrambled_25.txt WA 19 ms 712 KB
1
scrambled_26.txt WA 24 ms 716 KB
1
scrambled_27.txt WA 18 ms 636 KB
1
scrambled_28.txt WA 27 ms 676 KB
1
scrambled_29.txt WA 21 ms 704 KB
1
scrambled_30.txt WA 20 ms 716 KB
1
scrambled_31.txt WA 17 ms 760 KB
1
scrambled_32.txt WA 18 ms 772 KB
1
scrambled_33.txt WA 19 ms 692 KB
1
scrambled_34.txt WA 18 ms 712 KB
1
scrambled_35.txt WA 20 ms 760 KB
1
scrambled_36.txt WA 19 ms 792 KB
1
scrambled_37.txt WA 16 ms 696 KB
1
scrambled_38.txt AC 22 ms 756 KB
1
scrambled_39.txt AC 21 ms 696 KB
1
scrambled_40.txt AC 21 ms 628 KB
1
scrambled_41.txt WA 21 ms 696 KB
1
scrambled_42.txt WA 21 ms 636 KB
1
scrambled_43.txt AC 24 ms 704 KB
1
scrambled_44.txt AC 19 ms 772 KB
1
scrambled_45.txt AC 27 ms 708 KB
1
scrambled_46.txt AC 20 ms 780 KB
1
scrambled_47.txt AC 27 ms 724 KB
1
scrambled_48.txt AC 17 ms 796 KB
1
scrambled_49.txt AC 24 ms 864 KB
1
scrambled_50.txt AC 21 ms 808 KB
1
scrambled_51.txt AC 21 ms 752 KB
1
scrambled_52.txt WA 21 ms 824 KB
1
scrambled_53.txt AC 18 ms 700 KB
1