oj.uz

Submission #286642

# Submission time Handle Problem Language Result Execution time Memory
286642 2020-08-30T15:55:50 Z stoyan_malinin Toy Train (IOI17_train) C++14
16 / 100
 1166 ms 50872 KB 
#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;

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

    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][2];
void dfsMark(int x, int start, int depth, bool mode = false)
{
    if(depth!=0) reachable[start][x][mode] = true;
    for(int y: adj[x])
    {
        if(reachable[start][y][mode]==true) continue;
        if(mode==true && charging[y]==1) continue;

        dfsMark(y, start, depth+1, mode);
    }
}


vector <int> solve3()
{
    vector <int> res(n, -1);
    for(int i = 0;i<n;i++) dfsMark(i, i, 0, false);

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

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

        goodCycle[x] = ans;
        //cout << "goodCycle[" << x << "] = " << ans << '\n';
    }

    for(int s = 0;s<n;s++)
    {
        //cout << " ---- " << s << " --- " << '\n';

        res[s] = goodCycle[s];
        for(int x = 0;x<n;x++)
        {
            //cout << x << " -> " << reachable[s][x] << '\n';
            if(reachable[s][x][0]==true && goodCycle[x]==true)
            {
                res[s] = true;
                break;
            }
        }
    }

    return res;
}

vector <int> solve4()
{
    vector <int> res(n, -1);
    for(int i = 0;i<n;i++)
    {
        dfsMark(i, i, 0, false);
        dfsMark(i, i, 0, true);
    }

    vector <bool> goodCycle(n, false);
    for(int x = 0;x<n;x++)
    {
        if(charging[x]==true) continue;

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

        goodCycle[x] = ans;
        //cout << "goodCycle[" << x << "] = " << ans << '\n';
    }

    for(int s = 0;s<n;s++)
    {
        //cout << " ---- " << s << " --- " << '\n';

        res[s] = goodCycle[s];
        for(int x = 0;x<n;x++)
        {
            //cout << x << " -> " << reachable[s][x] << '\n';
            if(reachable[s][x][0]==true && goodCycle[x]==true)
            {
                res[s] = true;
                break;
            }
        }
    }

    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();
    else if(subtask==4) return solve4();

    return {};
}
/*
3 3
1 1 1
1 0 0
0 0
1 0
2 1
*/

Compilation message

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:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0;i<a.size();i++)
      |                   ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:281:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  281 |     for(int i = 0;i<u.size();i++)
      |                   ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 50524 KB Output is correct
2 Correct 405 ms 50872 KB Output is correct
3 Correct 446 ms 50664 KB Output is correct
4 Correct 1105 ms 50612 KB Output is correct
5 Correct 876 ms 50780 KB Output is correct
6 Correct 727 ms 50676 KB Output is correct
7 Correct 506 ms 50488 KB Output is correct
8 Correct 375 ms 50360 KB Output is correct
9 Correct 396 ms 50624 KB Output is correct
10 Correct 393 ms 50368 KB Output is correct
11 Correct 387 ms 50496 KB Output is correct
12 Correct 91 ms 46156 KB Output is correct
13 Correct 1160 ms 50740 KB Output is correct
14 Correct 1166 ms 50872 KB Output is correct
15 Correct 1161 ms 50612 KB Output is correct
16 Correct 1130 ms 50792 KB Output is correct
17 Correct 1141 ms 50748 KB Output is correct
18 Correct 629 ms 50424 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1280 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 4 ms 896 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Incorrect 1 ms 384 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -