Submission #420842

#	Time	Username	Problem	Language	Result	Execution time	Memory
420842		AugustinasJucas	Toy Train (IOI17_train)	C++14	5 / 100	10 ms	1612 KiB

train

//#include "train.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> charg;
vector<int> priklauso;
int n;
vector<bool> isEnd(5001, 0);
const int dydis = 5e3 + 10;
int ind[dydis] = {};
int low[dydis] = {};
int onS[dydis] = {};
vector<int> gr[dydis];
int dbInd = 0;
vector<int> st;
int sz[dydis] = {0};
vector<pair<int, int> > br;
void dfs(int v){
 	if(ind[v] == -1){
		ind[v] = dbInd;
		low[v] = dbInd++;
		onS[v] = 1;
		st.push_back(v);
	}
	
	for(auto x : gr[v]){
		if(ind[x] == -1){
			dfs(x);
			low[v] = min(low[x], low[v]);
		}else if(onS[x]){
			low[v] = min(low[v], ind[x]);
		}
	}
	if(low[v] == ind[v]){
		sz[low[v]] = 0;
		while(true){
			int u = st.back(); st.pop_back();
			low[u] = min(low[u], low[v]);
			onS[u] = 0;
			sz[low[v]]++;
			if(u == v) break;
		}
	}
}
vector<int> g[dydis];

set<pair<int, int> > setas;
bool arYra(int v){

	if(sz[v] > 1) return true;
	if(isEnd[v]) return true;
	bool ret = 0;
	for(auto x : g[v]){
		ret = ret | arYra(x);
	} 
	return ret;
}
vector<int> viskasPirmo(){
	vector<int> ret(n, 0);
	for(int i = 0; i < n; i++){
		if(ind[i] == -1) dfs(i);
	}
	for(auto x : br){
		int a = x.first;
		int b = x.second;
		if(low[a] == low[b]) continue; 
		if(setas.count({a, b})) continue;
		setas.insert({a, b});
		g[a].push_back(b);
	}
	for(int i = 0; i < n; i++){
		ret[i] = arYra(low[i]);
	}
	
	return ret;
}
vector<int> viskasAntro(){
	vector<int> ret(n);
	return ret;
}
vector<int> vienCharg(){
	vector<int> ret(n);
	return ret;
}

vector<int> prm(){
	vector<int> ret(n, 0);

	for(int i = 0; i < n; i++){
		int v = i;
	//	cout << "i  = " << i << endl;
		while(true){
		//	cout << "v = " << v << ", end = " << isEnd[v] << endl;
			if(isEnd[v] && priklauso[v] == charg[v]){
				ret[i] = priklauso[v];
				break;
			}else{
				if(gr[v].size() == 1 && gr[v][0] == v){
					ret[i] = charg[v];
					break;
				}else{
					v++;
				}
			}
		}
	}
	return ret;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	vector<int> res(a.size());
	priklauso = a;
	charg = r;
	n = a.size();
	for(int i = 0; i < n; i++) ind[i] = -1;
	for(int i = 0; i < (int)u.size(); i++){
		br.push_back({u[i], v[i]});
		gr[u[i]].push_back(v[i]);
	//	gr[v[i]].push_back(u[i]);
	}
	int cnt[2] = {0}; for(auto x : a) cnt[x]++;
	int rc = 0; for(auto x : r) rc += x;
	bool pirmasSub = 1;
	for(int i = 0 ; i < u.size(); i++) {
		if(v[i] == u[i]) isEnd[v[i]] = 1;
		if(v[i] - u[i] == 0 || v[i]-u[i] == 1) continue;
		pirmasSub = 0;
	}
	if(pirmasSub){
		return prm();
	}
	if(cnt[1] == 0){
		return viskasPirmo();
	}else if(cnt[0] == 0){
		return viskasAntro();
	}else if(rc == 0){
		return vienCharg();
	}
	//for(int i = 0; i < n; i++)
	
	return res;
}








/*

8 9
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 
0 1
1 2
1 3
3 4
4 5
5 3
2 7
7 6
6 2 


6 7
0 0 1 1 0 1
0 1 0 0 0 1
0 1
1 2
2 3
3 4
4 5
2 2
5 5



*/

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i = 0 ; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51