結果
問題 | No.583 鉄道同好会 |
ユーザー | manugino |
提出日時 | 2017-10-31 11:46:22 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 6,580 bytes |
コンパイル時間 | 823 ms |
コンパイル使用メモリ | 87,768 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-02 01:24:04 |
合計ジャッジ時間 | 1,730 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 6 ms
5,376 KB |
testcase_12 | AC | 8 ms
5,376 KB |
testcase_13 | AC | 8 ms
5,376 KB |
testcase_14 | AC | 8 ms
5,376 KB |
testcase_15 | AC | 11 ms
5,376 KB |
testcase_16 | AC | 18 ms
5,376 KB |
testcase_17 | AC | 21 ms
5,376 KB |
testcase_18 | AC | 21 ms
5,376 KB |
ソースコード
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // [Tips] // XCodeでのEOF入力はCtrl+D // ¥はAlt+\ // ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////// // //////////////////////////////////////// //#define debug //******************************************************************************************************************************************* #ifdef debug #include <chrono> #endif #include <iostream> #include <algorithm> // next_permutation #include <iomanip> #include <cmath> #include <vector> #include <sstream> #include <string> #include <cstring> //memcpy #include <cstdio> #include <stack> #include <queue> #include <list> #include <numeric> //accumulate //#include <map> //#include <unordered_map> //hash func. #include <fstream> //ifstream, ofstream #include <iterator> //insert_iterator::inserter #include <set> //#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code. #include <cassert> //assert using namespace std; #define dout cout //If u wanna output to a text file instead of standard output, plz define OUTPUTFILE. //#define OUTPUTFILE "output.txt" //************************************************************ #ifdef OUTPUTFILE #define dout outputfile ofstream outputfile(OUTPUTFILE); #define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt" #endif #define din cin //If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを. //#define INPUTFILE "input.txt" //************************************************************** #ifdef INPUTFILE #define din inputfile ifstream inputfile(INPUTFILE); #endif #define scand(A) scanf("%d", &(A)) #define scans(A) scanf("%s", (A)) #define printd(A) printf("%d\n", (A)) #define prints(A) printf("%s\n", (A)) #define disp(A) dout << #A << " = " << setw(3) << (A) << endl #define disP(A) dout << setw(3) << (A) << " " #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl #define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl #define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1 #define p(i) ((i)/2) #define l(i) ((i)*2) #define r(i) ((i)*2+1) #define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16) #define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1 #define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0 int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; typedef pair<int,int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef long long ll; typedef unsigned long long ull; const int INF = (1LL<<31)-1; const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow. const ull INF_ULL = (ull)1e19-1ULL; const int NONE = -1; //const ll MOD = (ll)1e9+7; //大きい素数の代表といえばこの人、10億7さん const int MOD = 16411; const int N_MAX = 510; //num of vertex or element const int M_MAX = 124760; //num of edge const int DATA_MAX = 1010; int N, M; int root[N_MAX]; int degree[N_MAX]; ii e[M_MAX]; int ans = 0; void init() { rep(i,0,N) { root[i] = i; degree[i] = 0; } } int find(int x) { if(root[x]==x) return x; else return root[x] = find(root[x]); } void unite(int x, int y) { x = find(x); y = find(y); root[x] = y; } bool checkIfOddDegreeAre0or2() { #ifdef debug dout << "--- checkIfOddDegreeAre0or2()\n"; #endif int numOfOddDegree = 0; rep(i,0,N) { if(degree[i]%2) { numOfOddDegree++; } #ifdef debug dout << "--\n"; disp(i); disp(degree[i]); disp(numOfOddDegree); #endif } if(numOfOddDegree==0 or numOfOddDegree==2) return true; else return false; } bool checkIfAllEdgesAreConnected() { bool ret = true; int r = find(e[0].first); #ifdef debug dout << "--- checkIfAllEdgesAreConnected()\n"; disp(e[0].first); disp(e[0].second); disp(r); #endif rep(i,1,M) { if(r != find(e[i].first)) ret = false; #ifdef debug dout << "--\n"; disp(e[i].first); disp(find(e[i].first)); disp(e[i].second); disp(find(e[i].second)); disp(ret); #endif } return ret; } void display() { #ifdef debug dout << "----\n"; dout << " "; showi(i, 0, N); dout << " "; show(root,0,N); show(degree,0,N); #endif } int main() { //cin, coutの高速化 *注意:cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように! cin.tie(0); //cinとcoutの同期を切る ios::sync_with_stdio(false); //iostreamとstdioの同期を切る //read input data // scand(N); din >> N >> M; init(); display(); int s, g; rep(i,0,M) { din >> s >> g; degree[s]++; degree[g]++; unite(s, g); e[i] = make_pair(s, g); } display(); //------------------------------------------------------------------------------------------ #ifdef debug //start timer auto startTime = chrono::system_clock::now(); #endif //------------------------------------------------------------------------------------------ #ifdef debug dout << "=== OUTPUT ===\n"; #endif if(checkIfAllEdgesAreConnected() and checkIfOddDegreeAre0or2()) dout << "YES" << endl; else dout << "NO" << endl; //------------------------------------------------------------------------------------------ #ifdef debug //stop timer auto endTime = chrono::system_clock::now(); auto dur = endTime - startTime; auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count(); dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n"; #endif //------------------------------------------------------------------------------------------ #ifdef INPUTFILE inputfile.close(); #endif #ifdef OUTPUTFILE outputfile.close(); cout << "\"" << OutputFilePath << "\"" << endl; #endif return 0; }