oj.uz

답안 #291462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291462 2020-09-05T10:51:35 Z abyyskit 장난감 기차 (IOI17_train) C++14
11 / 100
 943 ms 1432 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;
}

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 1152 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 360 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 1424 KB Output is correct
2 Correct 264 ms 1432 KB Output is correct
3 Correct 316 ms 1364 KB Output is correct
4 Correct 507 ms 1280 KB Output is correct
5 Correct 165 ms 1280 KB Output is correct
6 Correct 798 ms 1216 KB Output is correct
7 Correct 282 ms 1196 KB Output is correct
8 Correct 113 ms 1200 KB Output is correct
9 Correct 376 ms 1272 KB Output is correct
10 Correct 39 ms 1152 KB Output is correct
11 Correct 80 ms 1152 KB Output is correct
12 Correct 49 ms 1024 KB Output is correct
13 Correct 33 ms 1400 KB Output is correct
14 Correct 35 ms 1340 KB Output is correct
15 Correct 35 ms 1280 KB Output is correct
16 Correct 40 ms 1280 KB Output is correct
17 Correct 40 ms 1280 KB Output is correct
18 Correct 609 ms 1152 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 943 ms 1168 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 1280 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 1152 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -