oj.uz

Submission #286645

# Submission time Handle Problem Language Result Execution time Memory
286645 2020-08-30T16:00:12 Z stoyan_malinin Toy Train (IOI17_train) C++14
16 / 100
 1160 ms 50736 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);
        if(charging[i]==0) 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;
    }

    for(int s = 0;s<n;s++)
    {
        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
0 0 0
0 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:278:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |     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 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 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 0 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 349 ms 50548 KB Output is correct
2 Correct 404 ms 50488 KB Output is correct
3 Correct 466 ms 50736 KB Output is correct
4 Correct 1118 ms 50612 KB Output is correct
5 Correct 878 ms 50484 KB Output is correct
6 Correct 717 ms 50356 KB Output is correct
7 Correct 508 ms 50232 KB Output is correct
8 Correct 363 ms 50232 KB Output is correct
9 Correct 396 ms 50240 KB Output is correct
10 Correct 408 ms 50240 KB Output is correct
11 Correct 368 ms 50240 KB Output is correct
12 Correct 94 ms 46028 KB Output is correct
13 Correct 1138 ms 50484 KB Output is correct
14 Correct 1145 ms 50640 KB Output is correct
15 Correct 1160 ms 50612 KB Output is correct
16 Correct 1143 ms 50612 KB Output is correct
17 Correct 1130 ms 50484 KB Output is correct
18 Correct 613 ms 50296 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 971 ms 50396 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 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Incorrect 0 ms 384 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -