Submission #70484062

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7;
int n, m;
int ans;
int p[N];
int U[N], V[N];
set<int>E[N];
void Main(){
	cin >> n >> m;
	ans = n;
	L(t, 1, m) 
		cin >> U[t] >> V[t];
	L(i, 1, n) cin >> p[i];
	L(t, 1, m)
		E[p[U[t]]].insert(p[V[t]]);
	ans = 0;
	set<int>st = E[1];
	L(i, 2, n) {
		if(st.count(i)) {
			st = E[i];
		} else {
			++ans;
			//cout << "i = " << i << endl;
			for(auto&u : E[i]) {
				st.insert(u);
			}
		}
	}
	cout << ans << '\n';
	L(i, 1, n) {
		E[i].clear();
	}
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}

Submission Info

Submission Time
Task A - Communicate Topological Order
User zhoukangyang
Language C++ 17 (gcc 12.2)
Score 700
Code Size 921 Byte
Status AC
Exec Time 135 ms
Memory 62292 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 1
AC × 70
Set Name Test Cases
Sample sample.txt
All dense_1.txt, dense_10.txt, dense_2.txt, dense_3.txt, dense_4.txt, dense_5.txt, dense_6.txt, dense_7.txt, dense_8.txt, dense_9.txt, line_1.txt, line_10.txt, line_2.txt, line_3.txt, line_4.txt, line_5.txt, line_6.txt, line_7.txt, line_8.txt, line_9.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_2.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_3.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_4.txt, random_40.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt
Case Name Status Exec Time Memory
dense_1.txt AC 120 ms 61552 KiB
dense_10.txt AC 122 ms 61744 KiB
dense_2.txt AC 124 ms 61476 KiB
dense_3.txt AC 126 ms 61356 KiB
dense_4.txt AC 135 ms 61612 KiB
dense_5.txt AC 119 ms 62036 KiB
dense_6.txt AC 123 ms 61352 KiB
dense_7.txt AC 125 ms 61860 KiB
dense_8.txt AC 118 ms 61792 KiB
dense_9.txt AC 121 ms 61572 KiB
line_1.txt AC 76 ms 55628 KiB
line_10.txt AC 95 ms 58644 KiB
line_2.txt AC 93 ms 60188 KiB
line_3.txt AC 78 ms 55240 KiB
line_4.txt AC 72 ms 56328 KiB
line_5.txt AC 73 ms 54208 KiB
line_6.txt AC 84 ms 55296 KiB
line_7.txt AC 76 ms 59152 KiB
line_8.txt AC 85 ms 56684 KiB
line_9.txt AC 82 ms 55228 KiB
random_1.txt AC 129 ms 62172 KiB
random_10.txt AC 58 ms 53968 KiB
random_11.txt AC 112 ms 55780 KiB
random_12.txt AC 133 ms 62136 KiB
random_13.txt AC 114 ms 57468 KiB
random_14.txt AC 102 ms 57016 KiB
random_15.txt AC 133 ms 62100 KiB
random_16.txt AC 111 ms 58168 KiB
random_17.txt AC 105 ms 56676 KiB
random_18.txt AC 99 ms 58744 KiB
random_19.txt AC 95 ms 56452 KiB
random_2.txt AC 133 ms 62168 KiB
random_20.txt AC 130 ms 62064 KiB
random_21.txt AC 126 ms 61596 KiB
random_22.txt AC 132 ms 62192 KiB
random_23.txt AC 129 ms 61436 KiB
random_24.txt AC 112 ms 60216 KiB
random_25.txt AC 125 ms 60300 KiB
random_26.txt AC 63 ms 54340 KiB
random_27.txt AC 113 ms 59124 KiB
random_28.txt AC 131 ms 61988 KiB
random_29.txt AC 131 ms 62128 KiB
random_3.txt AC 65 ms 55160 KiB
random_30.txt AC 109 ms 56796 KiB
random_31.txt AC 112 ms 57824 KiB
random_32.txt AC 118 ms 59380 KiB
random_33.txt AC 87 ms 54372 KiB
random_34.txt AC 126 ms 61836 KiB
random_35.txt AC 117 ms 58708 KiB
random_36.txt AC 114 ms 56052 KiB
random_37.txt AC 129 ms 62136 KiB
random_38.txt AC 71 ms 55652 KiB
random_39.txt AC 120 ms 58324 KiB
random_4.txt AC 114 ms 59832 KiB
random_40.txt AC 55 ms 53852 KiB
random_5.txt AC 113 ms 56452 KiB
random_6.txt AC 131 ms 62044 KiB
random_7.txt AC 127 ms 62292 KiB
random_8.txt AC 124 ms 58340 KiB
random_9.txt AC 111 ms 55296 KiB
sample.txt AC 23 ms 50516 KiB
small_1.txt AC 49 ms 50392 KiB
small_2.txt AC 49 ms 50388 KiB
small_3.txt AC 50 ms 50244 KiB
small_4.txt AC 48 ms 50316 KiB
small_5.txt AC 49 ms 50244 KiB
small_6.txt AC 49 ms 50444 KiB
small_7.txt AC 49 ms 50392 KiB
small_8.txt AC 48 ms 50468 KiB
small_9.txt AC 33 ms 50392 KiB