oj.uz

Submission #1043329

# Submission time Handle Problem Language Result Execution time Memory
1043329 2024-08-04T08:20:36 Z amirhoseinfar1385 Keys (IOI21_keys) C++17
9 / 100
 96 ms 53376 KB 
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
vector<int>revadj[maxn],adj[maxn],allc[maxn],adjs[maxn];
int all[maxn],vis2[maxn],vis[maxn],n,m,par[maxn],nago[maxn];
vector<int>res;
deque<int>allv;

void dfs(int u){
	vis[u]=1;
	for(auto x:adj[u]){
		if(vis[x]==0){
			dfs(x);
		}
	}
	allv.push_front(u);
}

void sfd(int u,int had){
	vis2[u]=1;
	allc[had].push_back(u);
	par[u]=had;
	for(auto x:revadj[u]){
		if(vis2[x]==0){
			sfd(x,had);
		}
	}
}

void calcscc(){
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
		}
	}
	while((int)allv.size()>0){
		if(vis2[allv.front()]==0){
			sfd(allv.front(),allv.front());
		//	cout<<"hey: "<<allv.front()<<endl;
		//	for(auto x:allc[allv.front()]){
		//		cout<<x<<" ";
		//	}
		//	cout<<endl;
		}
		allv.pop_front();
	}
}

void calres(){
	for(int i=0;i<n;i++){
		for(auto x:adj[i]){
			if(par[i]!=par[x]){
				nago[par[i]]=1;
			}
		}
	}
	int mainres=n+1;
	for(int i=0;i<n;i++){
		if(par[i]==i&&nago[i]==0){
			mainres=min(mainres,(int)allc[i].size());
		}
	}
	for(int i=0;i<n;i++){
		if((int)allc[i].size()==mainres&&par[i]==i&&nago[i]==0){
			for(auto x:allc[i]){
				res[x]=1;
			}
		}	
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n=(int)r.size();
	m=(int)u.size();
	res.resize(n);
	for(int i=0;i<n;i++){
		all[i]=r[i];
	}
	for(int i=0;i<m;i++){
		if(all[u[i]]==c[i]){
			adj[u[i]].push_back(v[i]);
			revadj[v[i]].push_back(u[i]);
		}
		if(all[v[i]]==c[i]){
			adj[v[i]].push_back(u[i]);
			revadj[u[i]].push_back(v[i]);
		}
	}
	calcscc();
	calres();
	for(int i=0;i<n;i++){
		if(all[i]!=0&&res[i]==0){
			exit(23);
		}
	}
	return res;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28492 KB Output is correct
4 Correct 11 ms 28508 KB Output is correct
5 Correct 11 ms 28572 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 11 ms 28632 KB Output is correct
8 Correct 12 ms 28504 KB Output is correct
9 Correct 10 ms 28508 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28492 KB Output is correct
4 Correct 11 ms 28508 KB Output is correct
5 Correct 11 ms 28572 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 11 ms 28632 KB Output is correct
8 Correct 12 ms 28504 KB Output is correct
9 Correct 10 ms 28508 KB Output is correct
10 Runtime error 10 ms 28508 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28492 KB Output is correct
4 Correct 11 ms 28508 KB Output is correct
5 Correct 11 ms 28572 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 11 ms 28632 KB Output is correct
8 Correct 12 ms 28504 KB Output is correct
9 Correct 10 ms 28508 KB Output is correct
10 Runtime error 10 ms 28508 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28492 KB Output is correct
4 Correct 11 ms 28508 KB Output is correct
5 Correct 11 ms 28572 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 11 ms 28632 KB Output is correct
8 Correct 12 ms 28504 KB Output is correct
9 Correct 10 ms 28508 KB Output is correct
10 Runtime error 96 ms 53376 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28492 KB Output is correct
4 Correct 11 ms 28508 KB Output is correct
5 Correct 11 ms 28572 KB Output is correct
6 Correct 11 ms 28504 KB Output is correct
7 Correct 11 ms 28632 KB Output is correct
8 Correct 12 ms 28504 KB Output is correct
9 Correct 10 ms 28508 KB Output is correct
10 Runtime error 10 ms 28508 KB Execution failed because the return code was nonzero
11 Halted 0 ms 0 KB -