Submission #802068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802068	2023-08-02T09:30:37 Z	kirakaminski968	Toy Train (IOI17_train)	C++17	0 / 100	6 ms	1236 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> adj[5005];
vector<int> exc; 
vector<int> calc(vector<int> &a, vector<int> &v, int winner){
  vector<int> deg(n); 
  queue<int> q; 
  for(int i = 0;i<n;++i){
    if(exc[i]) continue; 
    for(auto x : adj[i]){
      if(!exc[x]) deg[x]++; 
    }
  }
  for(auto x : v){
    if(deg[x] > 0){
      deg[x] = 0; 
    }
    q.push(x); 
  }
  vector<int> res; 
  while(!q.empty()){
    int u = q.front(); q.pop(); 
    res.push_back(u); 
    for(auto x : adj[u]){
      if(exc[x]) continue; 
      if(a[x] == winner && deg[x] > 0){
        deg[x] = 0; 
        q.push(x); 
      }
      else if(a[x] != winner){
        deg[x]--; 
        if(deg[x] == 0) q.push(x); 
      }
    }
  }
  return res; 
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
  n = a.size(); m = u.size(); 
  vector<int> ans(n); 
  for(int i = 0;i<m;++i){
    adj[v[i]].push_back(u[i]); 
  }
  while(true){
    int alive = count(exc.begin(),exc.end(),0); 
    if(alive == 0) break; 
    vector<int> R; 
    for(int i = 0;i<n;++i){
      if(!exc[i] && r[i]) R.push_back(i); 
    }
    R = calc(a,R,1); 
    if(R.size() == alive){
      for(auto x : R){
        exc[x] = 1; 
        ans[x] = 1; 
      }
    }
    else{
      vector<int> rem(n); 
      for(auto x : R) rem[x] = 1; 
      R.clear(); 
      for(int i = 0;i<n;++i){
        if(!exc[i] && !rem[i]) R.push_back(i); 
      }
      R = calc(a,R,0); 
      for(auto x : R){
        exc[x] = 1; 
        ans[x] = 1; 
      }
    }
  }
  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:54:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if(R.size() == alive){
      |        ~~~~~~~~~^~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	852 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	340 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	5 ms	1196 KB	Output is correct
2	Correct	5 ms	1236 KB	Output is correct
3	Correct	5 ms	1236 KB	Output is correct
4	Incorrect	6 ms	1236 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-