結果
問題 | No.470 Inverse S+T Problem |
ユーザー | monolith |
提出日時 | 2019-03-04 13:26:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 2,488 bytes |
コンパイル時間 | 666 ms |
コンパイル使用メモリ | 78,316 KB |
実行使用メモリ | 11,972 KB |
最終ジャッジ日時 | 2024-06-01 22:57:24 |
合計ジャッジ時間 | 1,831 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
8,640 KB |
testcase_01 | AC | 3 ms
8,776 KB |
testcase_02 | AC | 4 ms
8,688 KB |
testcase_03 | AC | 3 ms
8,852 KB |
testcase_04 | AC | 4 ms
8,644 KB |
testcase_05 | AC | 3 ms
8,736 KB |
testcase_06 | AC | 3 ms
8,516 KB |
testcase_07 | AC | 3 ms
8,388 KB |
testcase_08 | AC | 3 ms
8,640 KB |
testcase_09 | AC | 2 ms
8,680 KB |
testcase_10 | AC | 3 ms
8,744 KB |
testcase_11 | AC | 4 ms
8,772 KB |
testcase_12 | AC | 3 ms
8,808 KB |
testcase_13 | AC | 3 ms
8,776 KB |
testcase_14 | AC | 3 ms
8,684 KB |
testcase_15 | AC | 3 ms
8,684 KB |
testcase_16 | AC | 3 ms
8,516 KB |
testcase_17 | AC | 3 ms
8,812 KB |
testcase_18 | AC | 3 ms
8,808 KB |
testcase_19 | AC | 3 ms
8,816 KB |
testcase_20 | AC | 4 ms
8,772 KB |
testcase_21 | AC | 4 ms
8,512 KB |
testcase_22 | AC | 3 ms
8,680 KB |
testcase_23 | AC | 3 ms
8,648 KB |
testcase_24 | AC | 4 ms
8,772 KB |
testcase_25 | AC | 3 ms
8,768 KB |
testcase_26 | AC | 3 ms
8,776 KB |
testcase_27 | AC | 3 ms
8,648 KB |
testcase_28 | AC | 3 ms
8,588 KB |
testcase_29 | AC | 18 ms
11,972 KB |
testcase_30 | AC | 4 ms
8,516 KB |
ソースコード
#define _USE_MATH_DEFINES #include <cstdio> #include <cstdlib> #include <iostream> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <map> using namespace std; typedef pair<long long int, long long int> P; long long int INF = 1e18; long long int MOD = 1e9 + 7; #define MAX_V 110000 int V; vector<int> G[MAX_V]; // グラフの隣接リスト表現 vector<int> rG[MAX_V];// 辺の向きを逆にしたグラフ vector<int> vs; // 帰りがけ順の並び bool used[MAX_V]; // すでに調べたか int cmp[MAX_V]; // 属する強連結成分のトポロジカル順序 // from から to への辺を張る関数 void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i]]){ dfs(G[v][i]); } } vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for(int i = 0; i < rG[v].size(); i++){ if(!used[rG[v][i]]){ rdfs(rG[v][i], k); } } } // 強連結成分分解を行う関数、返り値は強連結成分の個数 int scc(){ memset(used, 0, sizeof(used)); vs.clear(); for(int v = 0; v < V; v++){ if(!used[v]){ dfs(v); } } memset(used, 0, sizeof(used)); int k = 0; for(int i = vs.size() - 1; i >= 0; i--){ if(!used[vs[i]]){ rdfs(vs[i], k++); } } return k; } int main(){ int N; cin >> N; V = N * 2; if(N > 2000){ cout << "Impossible" << endl; return 0; } string S[2000]; for(int i = 0; i < N; i++){ cin >> S[i]; } for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ if(S[i][0] == S[j][0] || (S[i][1] == S[j][1] && S[i][2] == S[j][2])){ add_edge(i, j + N); add_edge(j, i + N); } if(S[i][0] == S[j][2] || (S[i][1] == S[j][0] && S[i][2] == S[j][1])){ add_edge(i, j); add_edge(j + N, i + N); } if(S[i][2] == S[j][0] || (S[i][0] == S[j][1] && S[i][1] == S[j][2])){ add_edge(i + N, j + N); add_edge(j, i); } if(S[i][2] == S[j][2] || (S[i][0] == S[j][0] && S[i][1] == S[j][1])){ add_edge(i + N, j); add_edge(j + N, i); } } } scc(); for(int i = 0; i < N; i++){ if(cmp[i] == cmp[i + N]){ cout << "Impossible" << endl; return 0; } } for(int i = 0; i < N; i++){ string str = " "; str[0] = S[i][0]; str[3] = S[i][2]; if(cmp[i] > cmp[i + N]){ str[2] = S[i][1]; }else{ str[1] = S[i][1]; } cout << str << endl; } return 0; }