Segments
Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in 阅读全文 »
TopCoder SRM#677(Div2)(2/3)
maksyuki 发表于 比赛 分类，标签: 比赛-topcoder
25
1月
2016
250 Problem Statement
A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ...
A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321.
A positive integer is called a palindromic prime if it is both a palindrome and a prime.
You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.
Definition
Class: PalindromePrime
Method: count
Parameters: int, int
Returns: int
Method signature: int count(int L, int R)
(be sure your method is public)
题目类型：暴力枚举
算法分析：直接循环枚举判断即可
|
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 |
// BEGIN CUT HERE // END CUT HERE #line 5 "PalindromePrime.cpp" #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; class PalindromePrime { public: int count(int L, int R) { int res = 0; for (int i = L; i <= R; i++) { if (i == 1) continue; bool is_find = true; for (int j = 2; j * j <= i; j++) if (i % j == 0) { is_find = false; break; } if (is_find) { string s; int tt = i; do { s += (char) (tt % 10 + '0'); tt /= 10; } while (tt); int len = s.size (); bool is_have = true; for (int i = 0; i < len / 2; i++) if (s[i] != s[len-1-i]) { is_have = false; break; } if (is_have) res++; } } return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { int Arg0 = 100; int Arg1 = 150; int Arg2 = 2; verify_case(0, Arg2, count(Arg0, Arg1)); } void test_case_1() { int Arg0 = 1; int Arg1 = 9; int Arg2 = 4; verify_case(1, Arg2, count(Arg0, Arg1)); } void test_case_2() { int Arg0 = 929; int Arg1 = 929; int Arg2 = 1; verify_case(2, Arg2, count(Arg0, Arg1)); } void test_case_3() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 0; verify_case(3, Arg2, count(Arg0, Arg1)); } void test_case_4() { int Arg0 = 1; int Arg1 = 1000; int Arg2 = 20; verify_case(4, Arg2, count(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE int main() { PalindromePrime ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
550 Problem Statement
We have four strings: a, b, c, and d.
A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist.
For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d.
Find and return the length of the shortest superstring of a, b, c, and d.
Definition
Class: FourStrings
Method: shortestLength
Parameters: string, string, string, string
Returns: int
Method signature: int shortestLength(string a, string b, string c, string d)
(be sure your method is public)
题目类型：暴力枚举+判断
算法分析：由于一共才有4!种排列，所以可以使用next_permutation函数来生成每个排列，然后先判断当前字符串si是否是res的子串，若是则直接判断下一个字符串si+1。否则枚举res后min(res_len, si_len) ~ 0个子串并和si的前len ~ 0个子串比较。将多出来的部分加到res的尾部。最后统计最小值即可
|
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 |
// BEGIN CUT HERE // END CUT HERE #line 5 "FourStrings.cpp" #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; vector <string> s; int res; void SS () { string ans = s[0]; for (int i = 1; i < 4; i++) { if (ans.find (s[i]) != string :: npos) continue; int len = min (ans.size (), s[i].size ()); while (len >= 0 && ans.substr (ans.size () - len).find (s[i].substr (0, len)) == string :: npos) len--; ans += s[i].substr (len); } res = min (res, (int) ans.size ()); } class FourStrings { public: int shortestLength(string a, string b, string c, string d) { s.clear (); s.push_back (a), s.push_back (b), s.push_back (c), s.push_back (d); sort (s.begin (), s.end ()); res = INF; do { SS (); } while (next_permutation (s.begin (), s.end ())); return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { string Arg0 = "abc"; string Arg1 = "ab"; string Arg2 = "bc"; string Arg3 = "b"; int Arg4 = 3; verify_case(0, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_1() { string Arg0 = "a"; string Arg1 = "bc"; string Arg2 = "def"; string Arg3 = "ghij"; int Arg4 = 10; verify_case(1, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_2() { string Arg0 = "top"; string Arg1 = "coder"; string Arg2 = "opco"; string Arg3 = "pcode"; int Arg4 = 8; verify_case(2, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_3() { string Arg0 = "thereare"; string Arg1 = "arelots"; string Arg2 = "lotsof"; string Arg3 = "ofcases"; int Arg4 = 19; verify_case(3, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_4() { string Arg0 = "aba"; string Arg1 = "b"; string Arg2 = "b"; string Arg3 = "b"; int Arg4 = 3; verify_case(4, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } void test_case_5() { string Arg0 = "x"; string Arg1 = "x"; string Arg2 = "x"; string Arg3 = "x"; int Arg4 = 1; verify_case(5, Arg4, shortestLength(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE }; // BEGIN CUT HERE int main() { FourStrings ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
poj3592
maksyuki 发表于 oj 分类，标签: DP-树形DP, 图论-有向图强连通分量
25
1月
2016
Instantaneous Transference
It was long ago when we played the game Red Alert. There is a magic function for the game objects which is called instantaneous transfer. When an object uses this magic function, it will be transferred to the specified point immediately, regardless of how far it is.
Now there is a mining area, and you are driving an ore-miner truck. Your mission is to take the maximum ores in the field.
The ore area is a rectangle region which is composed by n × m small squares, some of the squares have numbers of ores, while some do not. The ores can't be regenerated after taken.
The starting position of the ore-miner truck is the northwest corner of the field. It must move to the eastern or southern adjacent square, while it can not move to the northern or western adjacent square. And some squares have magic power that can instantaneously transfer the truck to a certain square specified. However, as the captain of the ore-miner truck, you can decide whether to use this magic power or to stay still. One magic power square will never lose its magic power; you can use the magic power whenever you get there.
Input
The first line of the input is an integer T which indicates the number of test cases.
For each of the test case, the first will be two integers N, M (2 ≤ N, M ≤ 40).
The next N lines will describe the map of the mine field. Each of the N lines will be a string that contains M characters. Each character will be an integer X (0 ≤ X ≤ 9) or a '*' or a '#'. The integer X indicates that square has X units of ores, which your truck could get them all. The '*' indicates this square has a magic power which can transfer truck within an instant. The '#' indicates this square is full of rock and the truck can't move on this square. You can assume that the starting position of the truck will never be a '#' square.
As the map indicates, there are K '*' on the map. Then there follows K lines after the map. The next K lines describe the specified target coordinates for the squares with '*', in the order from north to south then west to east. (the original point is the northwest corner, the coordinate is formatted as north-south, west-east, all from 0 to N - 1,M - 1).
Output
For each test case output the maximum units of ores you can take.
Sample Input
1
2 2
11
1*
0 0
Sample Output
3
Source
South Central China 2008 hosted by NUDT
题目类型：有向图强连通分量+缩点+树形DP
算法分析：每个非”#”点和左边、下边的点之间连一条有向边，若遇到”#”点则不连，当然需要将平面图的坐标重新映射一下。对于每个魔法点”*”，需要额外判断是否能够向其目标点连有向边(目标点非”#”才能连)。易知同一个强连通分量中的点可以双向可达，所以可以缩点，用其中所有点的val值的和来表示缩点后的点的点权，缩点后的图是一个有向无环图且没有重边，所以可以看做是树。使用dp[i]表示以i为根的子树所具有的最大价值。dp[i]初始化成对应缩点后的点权。状态转移方程为dp[u] = max (dp[u], vval[u] + dp[v])，vval[u]表示u点处的点权(缩点后)且v是u的子节点。最后输出顶点1所在缩点处的dp值即可
|
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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 |
/************************************************* Author :supermaker Created Time :2016/1/25 14:26:33 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 66 * 66 + 66; int dfn[maxn], low[maxn], belong[maxn], val[maxn], vval[maxn], dp[maxn]; int n, m, id, tot; char g[maxn][maxn]; bool instack[maxn]; vector <int> gg[maxn], ggg[maxn]; vector <PII> in; stack <int> sta; const int dx[] = {0, 1}; const int dy[] = {1, 0}; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < gg[u].size (); i++) { int v = gg[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; vval[tot] += val[tt]; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (vval, 0, sizeof (vval)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } void dp_dfs (int u) { for (int i = 0; i < ggg[u].size (); i++) { int v = ggg[u][i]; dp_dfs (v); dp[u] = max (dp[u], vval[u] + dp[v]); } } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &m); int k = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf (" %c", &g[i][j]); if (g[i][j] == '*') k++; } in.clear (); for (int i = 1; i <= k; i++) { int x, y; scanf ("%d%d", &x, &y); x++, y++; in.push_back (PII (x, y)); } for (int i = 0; i < maxn; i++) gg[i].clear (); k = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (g[i][j] == '#') { val[(i-1)*m+j] = 0; continue; } for (int q = 0; q < 2; q++) { int xx = i + dx[q], yy = j + dy[q]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#') gg[(i-1)*m+j].push_back ((xx - 1) * m + yy); } if (g[i][j] >= '0' && g[i][j] <= '9') val[(i-1)*m+j] = g[i][j] - '0'; else val[(i-1)*m+j] = 0; if (g[i][j] == '*') { int xx = in[k].first, yy = in[k].second; k++; if (g[xx][yy] != '#') gg[(i-1)*m+j].push_back ((xx - 1) * m + yy); } } n = m * n;//important!!! SS (); for (int i = 0; i < maxn; i++) ggg[i].clear (); for (int u = 1; u <= n; u++) for (int i = 0; i < gg[u].size (); i++) { int v = gg[u][i]; if (belong[u] != belong[v]) ggg[belong[u]].push_back (belong[v]); } for (int i = 1; i <= tot; i++) dp[i] = vval[i]; dp_dfs (belong[1]); printf ("%d\n", dp[belong[1]]); } return 0; } |
poj1904
maksyuki 发表于 oj 分类，标签: 图论-二分图完备匹配, 图论-有向图强连通分量
25
1月
2016
King's Quest
Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
Input
The first line of the input contains N -- the number of king's sons (1 <= N <= 2000). Next N lines for each of king's sons contain the list of the girls he likes: first Ki -- the number of those girls, and then Ki different integer numbers, ranging from 1 to N denoting the girls. The sum of all Ki does not exceed 200000.
The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
Output
Output N lines.For each king's son first print Li -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print Li different integer numbers denoting those girls, in ascending order.
Sample Input
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Sample Output
2 1 2
2 1 2
1 3
1 4
Hint
This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.
Source
题目类型：有向图强连通分量(二分图完备匹配)
算法分析：这道题直观上是一道求解二分图完备匹配并输出所有满足条件的问题。但是由于顶点数和边数比较多，所以直接使用找增广链的算法会超时。这里利用二分图完备匹配的性质来简化问题。如何才能不通过寻找增广链而直接确定是否存在增广链呢？让我们再次回到初始的想法，如果给定的完备匹配中xi -> yi，现在我们想让xi指向yj。如果让xi -> yj的话，那么yi显然对于xi已经没用了，又因为最终的匹配必然是一个完备匹配，即yi一定会被某一个xk(1 <= k <= n)所匹配。所以假如寻找到了增广链，那么增广链的最后一条边所指向的顶点必然是yi。假如我们由yi向xi再连一条边会发生什么呢？ 很明显，形成了一个环！也就是说，形成了一个强连通分量。所以说，如果xi可以选择yj(即xi喜欢yi且可以结婚)，那么xi和yj必然属于同一个强连通分量。所以此题可用强连通分量来求解，求解出强连通分量后直接统计即可
|
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 143 144 145 146 147 148 149 150 |
/************************************************* Author :supermaker Created Time :2016/1/25 12:38:12 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2 * 2000 + 66; int dfn[maxn], low[maxn], belong[maxn]; int n, id, tot; bool instack[maxn], gg[maxn][maxn]; vector <int> g[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 0; i < maxn; i++) g[i].clear (); memset (gg, false, sizeof (gg)); for (int i = 1; i <= n; i++) { int num; scanf ("%d", &num); for (int j = 1; j <= num; j++) { int u; scanf ("%d", &u); g[i].push_back (n + u); gg[i][u] = true; } } for (int i = 1; i <= n; i++) { int u; scanf ("%d", &u); g[n+u].push_back (i); } SS (); vector <int> temp; for (int i = 1; i <= n; i++) { temp.clear (); for (int j = n + 1; j <= 2 * n; j++) if (gg[i][j-n] && belong[i] == belong[j]) temp.push_back (j - n); sort (temp.begin (), temp.end ()); printf ("%d", temp.size ()); for (int j = 0; j < temp.size (); j++) printf (" %d", temp[j]); puts (""); } } return 0; } |