提出 #70487445

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m;
vector<int>adj[N],rev[N];
int ex[N],ey[N];
int p[N];

bool die[N];
void solve(){
	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		adj[i].clear();
		rev[i].clear();
		die[i]=false;
	}
	for(int i=1; i<=m ;i++){
		cin >> ex[i] >> ey[i];
	}
	for(int i=1; i<=n ;i++){
		cin >> p[i];
	}
	for(int i=1; i<=m ;i++){
		ex[i]=p[ex[i]];
		ey[i]=p[ey[i]];
		adj[ex[i]].push_back(ey[i]);
		rev[ey[i]].push_back(ex[i]);
	}
	int boss=1;
	int ans=0;
	for(int i=2; i<=n ;i++){
		bool win=false;
		for(auto c:rev[i]){
			if(c>=boss){
				win=true;
			}
		}
		if(!win){
			ans++;
		}
		else{
			boss=i;
		}
	}
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}

提出情報

提出日時
問題 A - Communicate Topological Order
ユーザ mulgokizary
言語 C++ 23 (gcc 12.2)
得点 700
コード長 844 Byte
結果 AC
実行時間 63 ms
メモリ 23452 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 700 / 700
結果
AC × 1
AC × 70
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
dense_1.txt AC 29 ms 10892 KiB
dense_10.txt AC 28 ms 8860 KiB
dense_2.txt AC 30 ms 13252 KiB
dense_3.txt AC 28 ms 10148 KiB
dense_4.txt AC 28 ms 8908 KiB
dense_5.txt AC 29 ms 9588 KiB
dense_6.txt AC 28 ms 10864 KiB
dense_7.txt AC 32 ms 15388 KiB
dense_8.txt AC 29 ms 11336 KiB
dense_9.txt AC 29 ms 10964 KiB
line_1.txt AC 40 ms 10848 KiB
line_10.txt AC 48 ms 16560 KiB
line_2.txt AC 48 ms 16724 KiB
line_3.txt AC 40 ms 14672 KiB
line_4.txt AC 41 ms 15396 KiB
line_5.txt AC 39 ms 9784 KiB
line_6.txt AC 42 ms 12000 KiB
line_7.txt AC 50 ms 23452 KiB
line_8.txt AC 43 ms 14168 KiB
line_9.txt AC 42 ms 12340 KiB
random_1.txt AC 61 ms 22648 KiB
random_10.txt AC 30 ms 16940 KiB
random_11.txt AC 49 ms 14652 KiB
random_12.txt AC 59 ms 22472 KiB
random_13.txt AC 48 ms 15940 KiB
random_14.txt AC 45 ms 16992 KiB
random_15.txt AC 62 ms 22468 KiB
random_16.txt AC 46 ms 13916 KiB
random_17.txt AC 42 ms 13888 KiB
random_18.txt AC 47 ms 20548 KiB
random_19.txt AC 39 ms 14096 KiB
random_2.txt AC 60 ms 22500 KiB
random_20.txt AC 59 ms 22612 KiB
random_21.txt AC 59 ms 22312 KiB
random_22.txt AC 62 ms 22540 KiB
random_23.txt AC 56 ms 19688 KiB
random_24.txt AC 53 ms 21480 KiB
random_25.txt AC 62 ms 21112 KiB
random_26.txt AC 28 ms 14656 KiB
random_27.txt AC 47 ms 14944 KiB
random_28.txt AC 61 ms 22448 KiB
random_29.txt AC 63 ms 22460 KiB
random_3.txt AC 33 ms 17956 KiB
random_30.txt AC 44 ms 13980 KiB
random_31.txt AC 47 ms 15660 KiB
random_32.txt AC 51 ms 16112 KiB
random_33.txt AC 38 ms 13708 KiB
random_34.txt AC 60 ms 22452 KiB
random_35.txt AC 45 ms 11484 KiB
random_36.txt AC 46 ms 14444 KiB
random_37.txt AC 59 ms 22484 KiB
random_38.txt AC 36 ms 18388 KiB
random_39.txt AC 44 ms 11376 KiB
random_4.txt AC 50 ms 18940 KiB
random_40.txt AC 28 ms 16756 KiB
random_5.txt AC 48 ms 14948 KiB
random_6.txt AC 60 ms 22448 KiB
random_7.txt AC 60 ms 22500 KiB
random_8.txt AC 45 ms 13924 KiB
random_9.txt AC 50 ms 16304 KiB
sample.txt AC 2 ms 3472 KiB
small_1.txt AC 18 ms 3528 KiB
small_2.txt AC 18 ms 3608 KiB
small_3.txt AC 18 ms 3556 KiB
small_4.txt AC 18 ms 3556 KiB
small_5.txt AC 18 ms 3496 KiB
small_6.txt AC 18 ms 3552 KiB
small_7.txt AC 18 ms 3524 KiB
small_8.txt AC 19 ms 3552 KiB
small_9.txt AC 9 ms 3548 KiB