oj.uz

Submission #419496

# Submission time Handle Problem Language Result Execution time Memory
419496 2021-06-07T07:55:34 Z 2fat2code Toy Train (IOI17_train) C++17
0 / 100
 10 ms 1228 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 5005;
const int mmax = 20005;

int n, m;
vector<int>nod[nmax];

void computeset(vector<int>&vecc, vector<int>&marked, vector<int>&host, int player){
    vector<int>cnt(n);
    for(int i=0;i<n;i++){
        for(auto it : nod[i]){
            if(marked[it] == 1 || vecc[it] == 1){
                cnt[i]++;
            }
        }
    }
    vector<int>procesare;
    for(int i=0;i<n;i++){
        if(!marked[i] && !vecc[i] && host[i] != player && cnt[i] == nod[i].size()){
            procesare.push_back(i);
        }
        else if(host[i] == player && !vecc[i]){
            for(auto it : nod[i]){
                if(vecc[it] == 1){
                    procesare.push_back(i);
                }
            }
        }
    }
    while(procesare.size()){
        auto it = procesare.back();
        procesare.pop_back();
        if(vecc[it] == 1){
            continue;
        }
        vecc[it] = 1;
        for(auto it1 : nod[it]){
            if(!marked[it1] && !vecc[it1]){
                if(host[it1] == player){
                    procesare.push_back(it1);
                }
                else{
                    cnt[it1]++;
                    if(cnt[it1] == (int)nod[it].size()){
                        procesare.push_back(it1);
                    }
                }
            }
        }
    }
}

void compute(vector<int>&marked, vector<int>&host, vector<int>&baterii){
    int cnt = 0;
    vector<int>r(n);
    for(int i=0;i<n;i++){
        if(baterii[i] == 1 && marked[i] == 0){
            r[i] = 1;
            cnt++;
        }
    }
    if(!cnt){
        for(int i=0;i<n;i++){
            marked[i] = 1;
        }
        return;
    }
    computeset(r, marked, host, 1);
    vector<int>b(n);
    cnt = 0;
    for(int i=0;i<n;i++){
        if(!marked[i] && !r[i]){
            b[i] = 1;
            cnt++;
        }
    }
    if(!cnt){
        return;
    }
    computeset(b, marked, host, 0);
    for(int i=0;i<n;i++){
        if(b[i] == 1){
            marked[i] = 1;
        }
    }
    compute(marked, host, baterii);
    return;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    int n = (int)a.size();
    int m = (int)u.size();
    for(int i=0;i<m;i++){
        nod[u[i]].push_back(v[i]);
        nod[v[i]].push_back(u[i]);
    }
    vector<int>ans(n);
    compute(ans, a, r);
    for(int i=0;i<n;i++) ans[i] ^= 1;
    return ans;
}

Compilation message

train.cpp: In function 'void computeset(std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
train.cpp:31:66: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if(!marked[i] && !vecc[i] && host[i] != player && cnt[i] == nod[i].size()){

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 716 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1100 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1228 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 716 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -