Submission #291460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
291460	2020-09-05T10:50:11 Z	abyyskit	Toy Train (IOI17_train)	C++14	11 / 100	1967 ms	1656 KB

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()){
		reset();
		mark(i, -1);
		if (g[i].pos) ans[i] = 1;
	}
	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";
	FOR(i, 0, a.size()){
		if (a[i] == 1){
			g[i].A = true;
		}
		if (r[i] == 1){
			g[i].charge = true;
		}
	}
//	cout << "here2" << "\n";
	return subtask3();
}

Compilation message

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 '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)
......
  151 |  FOR(i, 0, u.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:151:2: note: in expansion of macro 'FOR'
  151 |  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)
......
  155 |  FOR(i, 0, a.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:155:2: note: in expansion of macro 'FOR'
  155 |  FOR(i, 0, a.size()){
      |  ^~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	443 ms	1272 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	256 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	1436 KB	Output is correct
2	Correct	257 ms	1388 KB	Output is correct
3	Correct	281 ms	1404 KB	Output is correct
4	Correct	1967 ms	1332 KB	Output is correct
5	Correct	1270 ms	1528 KB	Output is correct
6	Correct	778 ms	1528 KB	Output is correct
7	Correct	810 ms	1528 KB	Output is correct
8	Correct	414 ms	1408 KB	Output is correct
9	Correct	369 ms	1384 KB	Output is correct
10	Correct	513 ms	1280 KB	Output is correct
11	Correct	404 ms	1400 KB	Output is correct
12	Correct	47 ms	1280 KB	Output is correct
13	Correct	1327 ms	1656 KB	Output is correct
14	Correct	1329 ms	1656 KB	Output is correct
15	Correct	1298 ms	1656 KB	Output is correct
16	Correct	1354 ms	1548 KB	Output is correct
17	Correct	1287 ms	1556 KB	Output is correct
18	Correct	607 ms	1276 KB	Output is correct