Submission #70188270

Source Code Expand

#include<iostream>
#include<vector>
#define pb push_back
using namespace std;
const int N=3e5+10;
int n,a[N],mx[N];
bool res,vis[N],c[N];
vector <int> tv,e[N],g[N];
void dfs0(int u,int fat)
{
	if(vis[u])
	{
		if(!tv.size())
		{
			tv.pb(u),u=a[u];
			while(u!=tv[0]) tv.pb(u),u=a[u];
		}
		return;
	}
	vis[u]=1;
	for(int v:g[u]) if(v!=fat) dfs0(v,u);
}
void dfs1(int u)
{
	mx[u]=u;
	for(int v:e[u]) if(!c[v]) dfs1(v),mx[u]=max(mx[u],mx[v]),res&=(mx[v]>u);
}
void sol()
{
	cin>>n,res=true;
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=n;i++) cin>>a[i],vis[i]=c[i]=0,e[a[i]].pb(i);
	for(int i=1;i<=n;i++) g[i]=e[i];
	for(int i=1;i<=n;i++) g[i].pb(a[i]);
	for(int i=1;i<=n;i++) if(!vis[i])
	{
		tv.clear(),dfs0(i,0);
		for(int x:tv) c[x]=1;
		for(int x:tv) dfs1(x);
		if(!res) {cout<<"No\n"; return;}
	}
	cout<<"Yes\n";
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol(); 
	return 0;
}

Submission Info

Submission Time
Task C - Ball Redistribution
User KSCD_
Language C++ 20 (gcc 12.2)
Score 1200
Code Size 993 Byte
Status AC
Exec Time 218 ms
Memory 52220 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 1
AC × 64
Set Name Test Cases
Sample 00-sample-001.txt
All 00-sample-001.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt, 01-025.txt, 01-026.txt, 01-027.txt, 01-028.txt, 01-029.txt, 01-030.txt, 01-031.txt, 01-032.txt, 01-033.txt, 01-034.txt, 01-035.txt, 01-036.txt, 01-037.txt, 01-038.txt, 01-039.txt, 01-040.txt, 01-041.txt, 01-042.txt, 01-043.txt, 01-044.txt, 01-045.txt, 01-046.txt, 01-047.txt, 01-048.txt, 01-049.txt, 01-050.txt, 01-051.txt, 01-052.txt, 01-053.txt, 01-054.txt, 01-055.txt, 01-056.txt, 01-057.txt, 01-058.txt, 01-059.txt, 01-060.txt, 01-061.txt, 01-062.txt, 01-063.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 6 ms 3596 KiB
01-001.txt AC 19 ms 3532 KiB
01-002.txt AC 6 ms 3552 KiB
01-003.txt AC 20 ms 3548 KiB
01-004.txt AC 20 ms 3440 KiB
01-005.txt AC 20 ms 3444 KiB
01-006.txt AC 20 ms 3552 KiB
01-007.txt AC 19 ms 3524 KiB
01-008.txt AC 21 ms 3772 KiB
01-009.txt AC 26 ms 4764 KiB
01-010.txt AC 152 ms 30552 KiB
01-011.txt AC 157 ms 30560 KiB
01-012.txt AC 103 ms 30576 KiB
01-013.txt AC 137 ms 30764 KiB
01-014.txt AC 111 ms 30616 KiB
01-015.txt AC 123 ms 31708 KiB
01-016.txt AC 124 ms 31560 KiB
01-017.txt AC 126 ms 31668 KiB
01-018.txt AC 125 ms 31636 KiB
01-019.txt AC 126 ms 31724 KiB
01-020.txt AC 218 ms 52220 KiB
01-021.txt AC 203 ms 49384 KiB
01-022.txt AC 26 ms 21372 KiB
01-023.txt AC 26 ms 21372 KiB
01-024.txt AC 122 ms 36292 KiB
01-025.txt AC 124 ms 37048 KiB
01-026.txt AC 122 ms 29464 KiB
01-027.txt AC 119 ms 29304 KiB
01-028.txt AC 150 ms 35272 KiB
01-029.txt AC 158 ms 34876 KiB
01-030.txt AC 126 ms 29772 KiB
01-031.txt AC 119 ms 29828 KiB
01-032.txt AC 166 ms 37216 KiB
01-033.txt AC 161 ms 37292 KiB
01-034.txt AC 78 ms 29140 KiB
01-035.txt AC 78 ms 29080 KiB
01-036.txt AC 123 ms 29512 KiB
01-037.txt AC 127 ms 29672 KiB
01-038.txt AC 137 ms 30148 KiB
01-039.txt AC 136 ms 30204 KiB
01-040.txt AC 199 ms 37284 KiB
01-041.txt AC 174 ms 37652 KiB
01-042.txt AC 80 ms 29152 KiB
01-043.txt AC 81 ms 29112 KiB
01-044.txt AC 131 ms 29948 KiB
01-045.txt AC 134 ms 29924 KiB
01-046.txt AC 141 ms 30260 KiB
01-047.txt AC 142 ms 30152 KiB
01-048.txt AC 167 ms 39212 KiB
01-049.txt AC 160 ms 39648 KiB
01-050.txt AC 82 ms 29084 KiB
01-051.txt AC 84 ms 28988 KiB
01-052.txt AC 133 ms 30080 KiB
01-053.txt AC 133 ms 30012 KiB
01-054.txt AC 161 ms 41104 KiB
01-055.txt AC 169 ms 39180 KiB
01-056.txt AC 73 ms 28088 KiB
01-057.txt AC 74 ms 28152 KiB
01-058.txt AC 185 ms 43344 KiB
01-059.txt AC 180 ms 45960 KiB
01-060.txt AC 93 ms 31968 KiB
01-061.txt AC 93 ms 31928 KiB
01-062.txt AC 147 ms 32868 KiB
01-063.txt AC 143 ms 34172 KiB