제출 #286581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286581		stoyan_malinin	장난감 기차 (IOI17_train)	C++14	5 / 100	402 ms	26932 KiB

train

#include "train.h"
//#include "grader.cpp"

#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 5005;

int n;
vector <int> adj[MAXN];
int owner[MAXN], charging[MAXN];

int guessSubtask(vector <int> a, vector <int> r, vector <int> u, vector <int> v)
{
    bool sub1 = true;
    for(int i = 0;i<u.size();i++)
    {
        if(u[i]!=v[i] && u[i]+1!=v[i])
        {
            sub1 = false;
            break;
        }
    }
    if(sub1==true) return 1;

    bool sub3 = true;
    for(int i = 0;i<a.size();i++)
    {
        if(a[i]!=1)
        {
            sub3 = false;
            break;
        }
    }
    if(sub3==true) return 3;

    return -1;
}

vector <int> solve1()
{
    vector <int> res(n, -1);

    for(int s = 0;s<n;s++)
    {
        int x = s;
        while(true)
        {
            int goal = -1;
            if(owner[x]==1)
            {
                if(charging[x]==1) goal = x;
                else goal = x + 1;

                bool found = false;
                for(int y: adj[x])
                {
                    if(y==goal)
                    {
                        found =true;
                        break;
                    }
                }

                if(found==true)
                {
                    if(goal==x)
                    {
                        res[s] = true;
                        break;
                    }
                    else
                    {
                        x = x + 1;
                    }
                }
                else
                {
                    if(goal==x)
                    {
                        x = x + 1;
                    }
                    else
                    {
                        res[s] = false;
                        break;
                    }
                }
            }
            else
            {
                if(charging[x]==1) goal = x + 1;
                else goal = x;

                bool found = false;
                for(int y: adj[x])
                {
                    if(y==goal)
                    {
                        found =true;
                        break;
                    }
                }

                if(found==true)
                {
                    if(goal==x)
                    {
                        res[s] = false;
                        break;
                    }
                    else
                    {
                        x = x + 1;
                    }
                }
                else
                {
                    if(goal==x)
                    {
                        x = x + 1;
                    }
                    else
                    {
                        res[s] = true;
                        break;
                    }
                }
            }
        }
    }

    return res;
}

bool reachable[MAXN][MAXN];
vector <int> solve3()
{
    vector <int> res(n, -1);

    function <void(int, int, int)> dfsMark = [&](int x, int start, int depth)
    {
        if(depth!=0) reachable[start][x] = true;
        for(int y: adj[x])
        {
            if(reachable[start][x]==false) dfsMark(y, start, depth+1);
        }
    };
    for(int i = 0;i<n;i++) dfsMark(i, i, 0);

    vector <int> chargingStations;
    for(int i = 0;i<n;i++)
    {
        if(charging[i]==1) chargingStations.push_back(i);
    }

    vector <int> inDeg(n, 0);
    for(int i = 0;i<n;i++)
    {
        for(int x: adj[i])
            inDeg[x]++;
    }

    vector <int> used(n, 0);
    function <bool(int)> solve = [&](int x)
    {
        if(res[x]!=-1)
            return bool(res[x]);

        if(used[x]>inDeg[x]) return false;
        used[x]++;

        bool ans = false;
        for(int station: chargingStations)
        {
            if(station==x) continue;
            if(reachable[x][station]==true && reachable[station][x]==true)
            {
                ans = true;
                break;
            }
        }
        if(charging[x]==true)
        {
            for(int i = 0;i<n;i++)
            {
                if(i==x) continue;
                if(reachable[x][i]==true && reachable[i][x]==true)
                {
                    ans = true;
                    break;
                }
            }
        }

        for(int y: adj[x])
        {
            if(y==x && charging[x]==1) ans = true;

            if(y==x) continue;
            ans |= solve(y);
        }

        res[x] = ans;
        return ans;
    };

    for(int iter = 0;iter<10;iter++)
    {
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<used.size();j++) used[j] = 0;

            res[i] = -1;
            res[i] = solve(i);
        }
    }

    return res;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    n = a.size();
    for(int i = 0;i<n;i++)
    {
        owner[i] = a[i];
        charging[i] = r[i];
    }

    for(int i = 0;i<u.size();i++)
    {
        adj[ u[i] ].push_back(v[i]);
    }

    for(int i = 0;i<n;i++)
    {
        sort(adj[i].begin(), adj[i].end());
        auto it = unique(adj[i].begin(), adj[i].end());
        adj[i].resize(it-adj[i].begin());
    }

    int subtask = guessSubtask(a, r, u, v);
    if(subtask==1) return solve1();
    else if(subtask==3) return solve3();

    return {};
}

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

train.cpp: In function 'int guessSubtask(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0;i<u.size();i++)
      |                   ~^~~~~~~~~
train.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0;i<a.size();i++)
      |                   ~^~~~~~~~~
train.cpp: In function 'std::vector<int> solve3()':
train.cpp:217:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |             for(int j = 0;j<used.size();j++) used[j] = 0;
      |                           ~^~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:236:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for(int i = 0;i<u.size();i++)
      |                   ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51