oj.uz

Submission #200556

# Submission time Handle Problem Language Result Execution time Memory
200556 2020-02-07T08:49:30 Z stefdasca Tenis (COI19_tenis) C++14
18 / 100
 500 ms 24392 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, q;
int ord[4][100002], poz[4][100002];

int nr;
bool viz[100002], viz2[100002];
vector<int>v[100002], tr[100002], ctc[100002];
stack<int>s;
void dfs(int nod)
{
    viz[nod] = 1;
    for(int j = 0; j < v[nod].size(); ++j)
    {
        int vecin = v[nod][j];
        if(!viz[vecin])
            dfs(vecin);
    }
    s.push(nod);
}
void dfs2(int nod)
{
    viz2[nod] = 1;
    ctc[nr].push_back(nod);
    for(int j = 0; j < tr[nod].size(); ++j)
    {
        int vecin = tr[nod][j];
        if(!viz2[vecin])
            dfs2(vecin);
    }
}

bool bst[100002];

void build()
{
    nr = 0;
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);
    while(!s.empty())
    {
        int nod = s.top();
        s.pop();
        if(!viz2[nod])
        {
            ++nr;
            dfs2(nod);
        }
    }
    for(int i = 0; i < ctc[1].size(); ++i)
        bst[ctc[1][i]] = 1;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for(int j = 1; j <= 3; ++j)
    {
        for(int i = 1; i <= n; ++i)
            cin >> ord[j][i], poz[j][ord[j][i]] = i;
        for(int i = 1; i < n; ++i)
        {
            v[ord[j][i]].pb(ord[j][i+1]);
            tr[ord[j][i+1]].pb(ord[j][i]);
        }
    }
    build();
    for(; q; --q)
    {
        int tip, val;
        cin >> tip;
        if(tip == 1)
        {
            cin >> val;
            cout << (bst[val] ? "DA" : "NE") << '\n';
        }
        else
        {
            int wh, a, b;
            cin >> wh >> a >> b;
            int x = poz[wh][a];
            int y = poz[wh][b];
            swap(ord[wh][x], ord[wh][y]);
            swap(poz[wh][a], poz[wh][b]);
            for(int j = 1; j <= n; ++j)
                v[j].clear(), tr[j].clear(), ctc[j].clear(), bst[j] = 0, viz[j] = viz2[j] = 0;
            for(int j = 1; j <= 3; ++j)
                for(int i = 1; i < n; ++i)
                {
                    v[ord[j][i]].pb(ord[j][i+1]);
                    tr[ord[j][i+1]].pb(ord[j][i]);
                }
            build();
        }
    }
    return 0;
}

Compilation message

tenis.cpp: In function 'void dfs(int)':
tenis.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < v[nod].size(); ++j)
                    ~~^~~~~~~~~~~~~~~
tenis.cpp: In function 'void dfs2(int)':
tenis.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < tr[nod].size(); ++j)
                    ~~^~~~~~~~~~~~~~~~
tenis.cpp: In function 'void build()':
tenis.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ctc[1].size(); ++i)
                    ~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 11 ms 7544 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 11 ms 7544 KB Output is correct
10 Correct 11 ms 7544 KB Output is correct
11 Correct 11 ms 7544 KB Output is correct
12 Correct 10 ms 7544 KB Output is correct
13 Correct 436 ms 24392 KB Output is correct
14 Execution timed out 527 ms 22892 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 21612 KB Output is correct
2 Execution timed out 79 ms 17880 KB Time limit exceeded (wall clock)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 11 ms 7544 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 11 ms 7544 KB Output is correct
10 Correct 11 ms 7544 KB Output is correct
11 Correct 11 ms 7544 KB Output is correct
12 Correct 10 ms 7544 KB Output is correct
13 Correct 436 ms 24392 KB Output is correct
14 Execution timed out 527 ms 22892 KB Time limit exceeded
15 Halted 0 ms 0 KB -