oj.uz

Submission #1068360

# Submission time Handle Problem Language Result Execution time Memory
1068360 2024-08-21T09:27:43 Z edogawa_something Toy Train (IOI17_train) C++17
11 / 100
 2000 ms 2048 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
vii adj[5001],radj[5001];
vector<int>a,r;
bool vis[5001],viss[5001],visss[5001];
void dfs(ll x) {
  if(vis[x])
    return;
  vis[x]=1;
  for(auto it:adj[x]) {
    if(!r[it])
    dfs(it);
  }
}
void rdfs(ll x) {
  if(viss[x])
    return;
  viss[x]=1;
  for(auto it:radj[x]) {
    if(!r[it])
    rdfs(it);
  }
}
void realrdfs(ll x) {
  if(visss[x])
    return;
  visss[x]=1;
  for(auto it:radj[x])
    realrdfs(it);
}
bool chk[5001];
vector<int>ans;
vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) {
  a=A,r=R;
  ans.resize(a.size());
  for(int i=0;i<u.size();i++)
    adj[u[i]].pb(v[i]),radj[v[i]].pb(u[i]);
  for(auto &it:ans)
    it=1;
  for(int i=0;i<a.size();i++) {
    if(r[i]==0) {
      for(int j=0;j<a.size();j++)
        vis[j]=viss[j]=visss[j]=0;
      dfs(i);
      rdfs(i);
      realrdfs(i);
      for(auto it:adj[i]) {
        if(it==i)
          chk[i]=1;
      }
      for(int j=0;j<a.size();j++) {
        if(j==i)
          continue;
        if(vis[j]&&viss[j])
          chk[i]=1;
      }
      if(chk[i]) {
        for(int j=0;j<a.size();j++) {
          ans[j]&=(1-visss[j]);
        }
      }
    }
  }
  return ans;
}

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:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
train.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i=0;i<a.size();i++) {
      |               ~^~~~~~~~~
train.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |       for(int j=0;j<a.size();j++)
      |                   ~^~~~~~~~~
train.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for(int j=0;j<a.size();j++) {
      |                   ~^~~~~~~~~
train.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j=0;j<a.size();j++) {
      |                     ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 1292 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 0 ms 600 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 472 ms 1924 KB Output is correct
2 Correct 275 ms 1628 KB Output is correct
3 Correct 167 ms 1624 KB Output is correct
4 Incorrect 1801 ms 1848 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 31 ms 1600 KB Output is correct
2 Correct 321 ms 1800 KB Output is correct
3 Correct 481 ms 1960 KB Output is correct
4 Correct 258 ms 1884 KB Output is correct
5 Correct 755 ms 1880 KB Output is correct
6 Correct 746 ms 1884 KB Output is correct
7 Correct 693 ms 1888 KB Output is correct
8 Correct 385 ms 1872 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 184 ms 2048 KB Output is correct
11 Correct 77 ms 2024 KB Output is correct
12 Correct 206 ms 1884 KB Output is correct
13 Correct 1313 ms 1880 KB Output is correct
14 Correct 700 ms 1880 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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