#149099 (C++11) No.482 あなたの名は

• 問題: No.482 あなたの名は
• ユーザー: IL_msta
• 提出日時: 2017-02-10 22:49:15
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 28 ms / 2,000 ms
• コード長: 2,253 bytes
• コンパイル時間: 1,890 ms
• コンパイル使用メモリ: 109,924 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-12-29 20:18:05
• 合計ジャッジ時間: 3,590 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 28

ソースコード

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
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <valarray>
//#include <array>//x C++ (G++ 4.6.4)
#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>
#include <cassert>//assert();
#include <fstream>
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#define PII pair<int,int>
/////////
using namespace::std;
// 最大公約数
template<class T>
inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}
// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a * b / gcd(a, b);}
////////////////////////////////
class UnionFind{
public:
    int cNum;//要素数
    vector<int> parent;
    UnionFind(int n){
        cNum = n;
        parent = vector<int>(n);
        for(int i=0;i<n;++i){parent[i] = i;}
    }
    int find(int x){
        if( parent[x] == x ){return x;}
        return parent[x] = find( parent[x] );
    }
    bool same(int x,int y){return find(x) == find(y);}
    void add(int x,int y){//union
        x = find(x);
        y = find(y);
        if( x==y )return;
        parent[x] = y;
    }
};
inline void solve(){
    int N;
    LL K;
    cin >> N >> K;
    vector<int> room(N);//現在の人番号
    for(int i=0;i<N;++i){
        cin >> room[i];
        --room[i];
    }
    ////
    UnionFind uf(N);
    int roomNo,inside;
    int num;
    vector<int> G;
    for(int i=0;i<N;++i){
        roomNo = i;
        inside = room[roomNo];
        num = 0;
        while( !uf.same(inside,roomNo) ){
            uf.add(inside,roomNo);
            roomNo = inside;
            inside = room[roomNo];
            ++num;
        }
        if( num ){
            G.push_back( num );
        }
    }
    int size = G.size();
    LL kaisuu = 0;
    for(int i=0;i<(int)size;++i){
        kaisuu += G[i];
    }
    if( K < kaisuu ){
        cout << "NO" << endl;
    }else if( (K - kaisuu)%2 == 0 ){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}
signed main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    //std::cout << std::fixed;//小数を10進数表示
    //cout << setprecision(16);//小数をいっぱい表示する。16?
    solve();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX