Submission #291475

#	Time	Username	Problem	Language	Result	Execution time	Memory
291475		abyyskit	Toy Train (IOI17_train)	C++14	37 / 100	1371 ms	1528 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back


struct node{
	vector<int> e;
	bool charge = false;
	bool A = false;
	bool vis = false;
	int time = INT_MAX;
	bool pos = false;
};

vector<node> g;

vector<int> subtask1(){
	vector<int> ans(g.size(), 0);
	for(int i = g.size() - 1; i >= 0; --i){
		if (g[i].A){
			ans[i] = 0;
		}
		else{
			ans[i] = 1;
		}
		FOR(j, 0, g[i].e.size()){
			int nex = g[i].e[j];
		//	cout << "nex: " << nex << "\n";
			if (g[i].A){
				if (g[i].charge && nex == i){
					ans[i] = 1;
					break;
				}
				if (nex != i){
					ans[i] = max(ans[i], ans[i + 1]);
				}
			}
			else{
				if (nex == i){
					if (!g[i].charge){
						ans[i] = 0;
						break;
					}
				}
				else{
					ans[i] = min(ans[i], ans[i + 1]);
				}
			}
		}
	}
	return ans;
}

int s2dfs(int start, int prev){
	g[start].vis = true;
	if (g[start].charge){
		prev = g[start].time;
	}
	int ans;
	if (g[start].A){
		ans = 0;
	}
	else{
		ans = 1;
	}
	FOR(i, 0, g[start].e.size()){
		int nex = g[start].e[i];
		if (!g[nex].vis){
			g[nex].time = g[start].time + 1;
			int tmp = s2dfs(nex, prev);
			if (g[start].A){
				ans = max(ans, tmp);
			}
			else{
				ans = min(ans, tmp);
			}
		}
		else{
			if (g[nex].time <= prev){
				if (g[start].A){
					ans = 1;
				}	
			}
			else{
				if (!g[start].A){
					ans = 0;
				}
			}
		}
	}
	g[start].time = INT_MAX;
	g[start].vis = false;
	return ans;
}


vector<int> subtask2(){
	vector<int> ans(g.size(), 0);
	FOR(i, 0, g.size()){
		g[i].time = 0;
		ans[i] = s2dfs(i, -1);
		g[i].time = INT_MAX;
	}
	return ans;
}

void reset(){
	FOR(i, 0, g.size()){
		g[i].vis = false;
	}
}

void mark(int cur, int start){
	g[cur].vis = true;
	FOR(i, 0, g[cur].e.size()){
		int nex = g[cur].e[i];
		if (nex == start){
			g[cur].pos = true;
		}
		if (!g[nex].vis){
			mark(nex, start);
		}
		if (g[nex].pos){
			g[cur].pos = true;
		}
	}

}


vector<int> subtask3(){
	vector<int> ans(g.size(), 0);
	FOR(i, 0, g.size()){
		if (g[i].charge){
			reset();
			mark(i, i);
		}
	}
	FOR(i, 0, g.size()){
		if (g[i].pos){
			ans[i] = 1;
		}
		else{
			reset();
			mark(i, -1);
		}
		if (g[i].pos) ans[i] = 1;
	}
	return ans;
}

void Mark(int cur, int start){
	g[cur].vis = true;
	FOR(i, 0, g[cur].e.size()){
		int nex = g[cur].e[i];
		if (!g[nex].charge){
			if (nex == start){
				g[cur].pos = true;
			}
			if (!g[nex].vis && !g[nex].pos){
				Mark(nex, start);
			}
			if (g[nex].pos){
				g[cur].pos = true;
			}
		}
	}
}

void check(int start){
	g[start].vis = true;
	FOR(i, 0, g[start].e.size()){
		int nex = g[start].e[i];
		if (!g[nex].vis && !g[nex].pos){
			check(nex);
		}
		if (g[nex].pos){
			g[start].pos = true;
		}
	}
}

vector<int> subtask4(){
	vector<int> ans(g.size(), 1);
	FOR(i, 0, g.size()){
		if (!g[i].charge){
			reset();
			Mark(i, i);
		}
	}
	FOR(i, 0, g.size()){
		if (g[i].pos){
			ans[i] = 0;
		}
		else{
			reset();
			check(i);
		}
		if (g[i].pos){
			ans[i] = 0;
		}


	}
	return ans;

}


vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
	g.resize(a.size());
	FOR(i, 0, u.size()){
		g[u[i]].e.pb(v[i]);
	}
//	cout << "here\n";
	int sum = 0;
	FOR(i, 0, a.size()){
		if (a[i] == 1){
			sum++;
			g[i].A = true;
		}
		if (r[i] == 1){
			g[i].charge = true;
		}
	}
	if (a.size() <= 15){
		return subtask2();
	}
	else if (sum == a.size()){
		return subtask3();
	}
	else if (sum == 0){
		return subtask4();
	}
	else{
		return subtask1();
	}
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> subtask1()':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   28 |   FOR(j, 0, g[i].e.size()){
      |       ~~~~~~~~~~~~~~~~~~~              
train.cpp:28:3: note: in expansion of macro 'FOR'
   28 |   FOR(j, 0, g[i].e.size()){
      |   ^~~
train.cpp: In function 'int s2dfs(int, int)':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   68 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
train.cpp:68:2: note: in expansion of macro 'FOR'
   68 |  FOR(i, 0, g[start].e.size()){
      |  ^~~
train.cpp: In function 'std::vector<int> subtask2()':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  101 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:101:2: note: in expansion of macro 'FOR'
  101 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp: In function 'void reset()':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  110 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:110:2: note: in expansion of macro 'FOR'
  110 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp: In function 'void mark(int, int)':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  117 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
train.cpp:117:2: note: in expansion of macro 'FOR'
  117 |  FOR(i, 0, g[cur].e.size()){
      |  ^~~
train.cpp: In function 'std::vector<int> subtask3()':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  135 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:135:2: note: in expansion of macro 'FOR'
  135 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  141 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:141:2: note: in expansion of macro 'FOR'
  141 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp: In function 'void Mark(int, int)':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  156 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
train.cpp:156:2: note: in expansion of macro 'FOR'
  156 |  FOR(i, 0, g[cur].e.size()){
      |  ^~~
train.cpp: In function 'void check(int)':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  174 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
train.cpp:174:2: note: in expansion of macro 'FOR'
  174 |  FOR(i, 0, g[start].e.size()){
      |  ^~~
train.cpp: In function 'std::vector<int> subtask4()':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  187 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:187:2: note: in expansion of macro 'FOR'
  187 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  193 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:193:2: note: in expansion of macro 'FOR'
  193 |  FOR(i, 0, g.size()){
      |  ^~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  214 |  FOR(i, 0, u.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:214:2: note: in expansion of macro 'FOR'
  214 |  FOR(i, 0, u.size()){
      |  ^~~
train.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
  219 |  FOR(i, 0, a.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:219:2: note: in expansion of macro 'FOR'
  219 |  FOR(i, 0, a.size()){
      |  ^~~
train.cpp:231:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |  else if (sum == a.size()){
      |           ~~~~^~~~~~~~~~~

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