oj.uz

Submission #292529

# Submission time Handle Problem Language Result Execution time Memory
292529 2020-09-07T08:37:57 Z dandrozavr Toy Train (IOI17_train) C++14
21 / 100
 1333 ms 1664 KB 
#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{
		}
		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

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)
......
  154 |  FOR(i, 0, g[cur].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~             
train.cpp:154:2: note: in expansion of macro 'FOR'
  154 |  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)
......
  172 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
train.cpp:172:2: note: in expansion of macro 'FOR'
  172 |  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)
......
  185 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:185:2: note: in expansion of macro 'FOR'
  185 |  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)
......
  191 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:191:2: note: in expansion of macro 'FOR'
  191 |  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)
......
  212 |  FOR(i, 0, u.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:212:2: note: in expansion of macro 'FOR'
  212 |  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)
......
  217 |  FOR(i, 0, a.size()){
      |      ~~~~~~~~~~~~~~                    
train.cpp:217:2: note: in expansion of macro 'FOR'
  217 |  FOR(i, 0, a.size()){
      |  ^~~
train.cpp:229:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |  else if (sum == a.size()){
      |           ~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 18 ms 1024 KB Output is correct
8 Incorrect 19 ms 1028 KB 3rd lines differ - on the 7th token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 110 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 43 ms 368 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 25 ms 376 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 404 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1408 KB Output is correct
2 Correct 36 ms 1528 KB Output is correct
3 Correct 69 ms 1536 KB Output is correct
4 Incorrect 449 ms 1664 KB 3rd lines differ - on the 13th token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 1296 KB Output is correct
2 Correct 171 ms 1280 KB Output is correct
3 Correct 113 ms 1408 KB Output is correct
4 Correct 19 ms 1408 KB Output is correct
5 Correct 224 ms 1408 KB Output is correct
6 Correct 388 ms 1400 KB Output is correct
7 Correct 329 ms 1376 KB Output is correct
8 Correct 57 ms 1280 KB Output is correct
9 Correct 37 ms 1280 KB Output is correct
10 Correct 1333 ms 1408 KB Output is correct
11 Correct 1316 ms 1528 KB Output is correct
12 Correct 1322 ms 1528 KB Output is correct
13 Correct 94 ms 1408 KB Output is correct
14 Correct 122 ms 1280 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 18 ms 1024 KB Output is correct
8 Incorrect 19 ms 1028 KB 3rd lines differ - on the 7th token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -