oj.uz

Submission #291471

# Submission time Handle Problem Language Result Execution time Memory
291471 2020-09-05T11:02:08 Z abyyskit Toy Train (IOI17_train) C++14
11 / 100
 1359 ms 1528 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{
			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";
	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 subtask4();
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 896 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
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 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1408 KB Output is correct
2 Correct 31 ms 1280 KB Output is correct
3 Correct 27 ms 1152 KB Output is correct
4 Incorrect 24 ms 1280 KB 3rd lines differ - on the 1st 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 1024 ms 1136 KB Output is correct
2 Correct 181 ms 1400 KB Output is correct
3 Correct 114 ms 1408 KB Output is correct
4 Correct 20 ms 1400 KB Output is correct
5 Correct 225 ms 1528 KB Output is correct
6 Correct 394 ms 1400 KB Output is correct
7 Correct 324 ms 1400 KB Output is correct
8 Correct 56 ms 1280 KB Output is correct
9 Correct 37 ms 1280 KB Output is correct
10 Correct 1330 ms 1508 KB Output is correct
11 Correct 1316 ms 1528 KB Output is correct
12 Correct 1359 ms 1504 KB Output is correct
13 Correct 96 ms 1528 KB Output is correct
14 Correct 119 ms 1280 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1280 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 Incorrect 15 ms 896 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -