oj.uz

답안 #778484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778484 2023-07-10T11:06:24 Z I_Love_EliskaM_ 장난감 기차 (IOI17_train) C++14
16 / 100
 844 ms 1636 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define ll long long

vector<int> p1(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> s(n);
	vector<int> f(n);
	vector<int> ans(n);
	forn(i,m) if (u[i]==v[i]) s[u[i]]=1;
	forn(i,m) if (u[i]!=v[i]) f[u[i]]=1;
	int now=0;
	for (int i=n-1; i>=0; --i) {
		if (s[i]) {
			if (now) {
				if (!a[i]) {
					if (!r[i]) now=0;
				} else {
					if (f[i]) now=1;
					else now = r[i];
				}
			} else {
				if (a[i]) {
					if (r[i]) now=1;
				} else {
					if (f[i]) now=0;
					else now = r[i];
				}
			}
		}
		ans[i]=now;
	}
	return ans;
}

const int N=5555;
vector<int> adj[N];
int vis[N];
int ok[N];
int dfs(int u, int s) {
	if (vis[u] && u==s) return 1;
	if (vis[u]) return 0;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) z|=dfs(v,s);
	return z;
}
int dfs2(int u) {
	if (ok[u]) return 1;
	if (vis[u]) return 0;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) z|=dfs2(v);
	return z;
}
vector<int> p3(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> ans(n);
	forn(i,m) adj[u[i]].pb(v[i]);
	forn(i,n) if (r[i]) {
		forn(j,n) vis[j]=0;
		int q=dfs(i,i);
		ok[i]=q;
	}
	forn(i,n) {
		forn(j,n) vis[j]=0;
		int q=dfs2(i);
		ans[i]=q;
	}
	return ans;
}

vector<int> p4(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> s(n);
	vector<int> ans(n);
	forn(i,m) if (u[i]==v[i]) s[i]=1;
	int now;
	for (int i=n-1; i>=0; --i) {
		if (s[i]) now=a[i];
		ans[i]=now;
	}
	return ans;
}

vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {

	int n=a.size(), m=u.size();
	int z=1;
	forn(i,m) z&=(u[i]==v[i]) || (v[i]==(u[i]+1));
	if (z) {
		return p1(a,r,u,v);
	}
	z=1;
	forn(i,n) z&=a[i];
	if (z) return p3(a,r,u,v);
	forn(i,n) z|=a[i];
	if (!z) return p4(a,r,u,v);

}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^
train.cpp: In function 'std::vector<int> p4(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:84:9: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |   ans[i]=now;

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 660 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 1504 KB Output is correct
2 Correct 121 ms 1480 KB Output is correct
3 Correct 137 ms 1548 KB Output is correct
4 Correct 729 ms 1404 KB Output is correct
5 Correct 581 ms 1612 KB Output is correct
6 Correct 442 ms 1508 KB Output is correct
7 Correct 208 ms 1480 KB Output is correct
8 Correct 202 ms 1492 KB Output is correct
9 Correct 176 ms 1452 KB Output is correct
10 Correct 258 ms 1436 KB Output is correct
11 Correct 222 ms 1400 KB Output is correct
12 Correct 20 ms 1364 KB Output is correct
13 Correct 822 ms 1636 KB Output is correct
14 Correct 844 ms 1628 KB Output is correct
15 Correct 759 ms 1624 KB Output is correct
16 Correct 805 ms 1620 KB Output is correct
17 Correct 835 ms 1620 KB Output is correct
18 Correct 252 ms 1268 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 660 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Runtime error 1 ms 596 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -