제출 #419517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419517		2fat2code	장난감 기차 (IOI17_train)	C++17	0 / 100	9 ms	1356 KiB

train

#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], nod1[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] || vecc[it]){
                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] && !marked[i]){
            for(auto it : nod[i]){
                if(vecc[it]){
                    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 : nod1[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]);
        nod1[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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51