oj.uz

Submission #286597

# Submission time Handle Problem Language Result Execution time Memory
286597 2020-08-30T15:13:43 Z stoyan_malinin Toy Train (IOI17_train) C++14
16 / 100
 1237 ms 26548 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;

    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][y]==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 <bool> goodCycle(n, false);
    for(int x = 0;x<n;x++)
    {
        bool ans = false;
        for(int station: chargingStations)
        {
            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;
                }
            }
        }

        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]==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();

    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: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:219:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |     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 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 4 ms 1024 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 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 369 ms 26548 KB Output is correct
2 Correct 415 ms 26160 KB Output is correct
3 Correct 473 ms 26172 KB Output is correct
4 Correct 1191 ms 26036 KB Output is correct
5 Correct 911 ms 25848 KB Output is correct
6 Correct 737 ms 25908 KB Output is correct
7 Correct 519 ms 25656 KB Output is correct
8 Correct 380 ms 25808 KB Output is correct
9 Correct 407 ms 25664 KB Output is correct
10 Correct 439 ms 25900 KB Output is correct
11 Correct 380 ms 25664 KB Output is correct
12 Correct 84 ms 25292 KB Output is correct
13 Correct 1224 ms 26292 KB Output is correct
14 Correct 1224 ms 26204 KB Output is correct
15 Correct 1237 ms 26268 KB Output is correct
16 Correct 1224 ms 26164 KB Output is correct
17 Correct 1216 ms 26168 KB Output is correct
18 Correct 634 ms 25976 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1152 KB WA in grader: Wrong returned array size
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 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 7 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 4 ms 1024 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 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 -