oj.uz

Submission #216493

# Submission time Handle Problem Language Result Execution time Memory
216493 2020-03-27T11:35:26 Z emil_physmath Simurgh (IOI17_simurgh) C++17
30 / 100
 424 ms 10232 KB 
#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define query count_common_roads
const int maxN = 500;
struct Jmp
{
    int to, ind;
    operator int&() { return to; }
    operator const int&() const { return to; }
};

int in[maxN], out[maxN];
Jmp par[maxN];
int gold[maxN * maxN];
vector<int> dfsq;
vector<Jmp> nei[maxN];
vector<int> same[maxN * maxN];
Jmp fup[maxN];

inline bool Upper(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; }
bool used[maxN];
void DFS(int v, Jmp p)
{
    // cerr << "v: " << v << '\n';
    static int time = 0;
    used[v] = true;
    in[v] = ++time;
    par[v] = p;
    fup[v] = {-1, -1};
    for (Jmp to: nei[v])
        if (!used[to])
        {
            dfsq.push_back(to.ind);
            DFS(to, {v, to.ind});
            if (p != -1)
                if (fup[v] == -1 || (fup[to] != -1 && in[fup[to]] <= in[fup[v]]))
                    fup[v] = fup[to];
        }
        else if (to != p && p != -1)
            if (fup[v] == -1 || in[to] <= in[fup[v]])
                fup[v] = to;
    out[v] = time;
}

void DFS1(int v)
{
    for (int to: same[v])
        if (gold[to] == -1)
        {
            gold[to] = gold[v];
            DFS1(to);
        }
}
vector<int> find_roads(int n, vector<int> us, vector<int> vs)
{
    int m = us.size();
    fill(gold, gold + m, -1);
    for (int i = 0; i < m; ++i)
    {
        nei[us[i]].push_back({vs[i], i});
        nei[vs[i]].push_back({us[i], i});
    }
    DFS(0, {-1, -1});
    // for (int i = 0; i < n; ++i)
        // cerr << "fup[" << i << "] = " << fup[i].to << '\n';
    int dfsans = query(dfsq);
    for (int i = 0; i < m; ++i)
        if (in[us[i]] > in[vs[i]])
            swap(us[i], vs[i]);
    for (int i = 0; i < m; ++i)
    {
        int u = us[i], v = vs[i];
        if (fup[v] == -1 || in[fup[v]] > in[u]) // Is a birdge.
        {
            gold[i] = 1;
            continue;
        }
        if (par[v] == u) continue;
        while (true)
        {
            int backe = i, dfse = par[v].ind;
            cerr << dfse << ' ' << backe << '\n';
            int j = find(dfsq.begin(), dfsq.end(), dfse) - dfsq.begin();
            dfsq[j] = backe;
            int curans = query(dfsq);
            if (curans == dfsans)
            {
                same[backe].push_back(dfse);
                same[dfse].push_back(backe);
            }
            else if (curans > dfsans)
                gold[backe] = 1, gold[dfse] = 0;
            else
                gold[backe] = 0, gold[dfse] = 1;
            dfsq[j] = dfse;
            if ((v = par[v]) == u) break;
        }
    }
    for (int i = 0; i < m; ++i)
        if (gold[i] != -1)
            DFS1(i);
    vector<int> ans;
    for (int i = 0; i < m; ++i)
        if (gold[i] == 1)
            ans.push_back(i);
    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB correct
2 Correct 8 ms 6272 KB correct
3 Correct 8 ms 6272 KB correct
4 Correct 8 ms 6272 KB correct
5 Correct 8 ms 6272 KB correct
6 Correct 8 ms 6272 KB correct
7 Correct 8 ms 6272 KB correct
8 Correct 8 ms 6272 KB correct
9 Correct 8 ms 6272 KB correct
10 Correct 8 ms 6272 KB correct
11 Correct 9 ms 6272 KB correct
12 Correct 8 ms 6272 KB correct
13 Correct 8 ms 6272 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB correct
2 Correct 8 ms 6272 KB correct
3 Correct 8 ms 6272 KB correct
4 Correct 8 ms 6272 KB correct
5 Correct 8 ms 6272 KB correct
6 Correct 8 ms 6272 KB correct
7 Correct 8 ms 6272 KB correct
8 Correct 8 ms 6272 KB correct
9 Correct 8 ms 6272 KB correct
10 Correct 8 ms 6272 KB correct
11 Correct 9 ms 6272 KB correct
12 Correct 8 ms 6272 KB correct
13 Correct 8 ms 6272 KB correct
14 Correct 184 ms 6708 KB correct
15 Correct 182 ms 6648 KB correct
16 Correct 197 ms 6648 KB correct
17 Correct 159 ms 6648 KB correct
18 Correct 58 ms 6392 KB correct
19 Correct 159 ms 6520 KB correct
20 Correct 148 ms 6520 KB correct
21 Correct 146 ms 6520 KB correct
22 Correct 81 ms 6520 KB correct
23 Correct 63 ms 6392 KB correct
24 Correct 54 ms 6392 KB correct
25 Correct 9 ms 6272 KB correct
26 Correct 53 ms 6272 KB correct
27 Correct 60 ms 6272 KB correct
28 Correct 18 ms 6272 KB correct
29 Correct 12 ms 6272 KB correct
30 Correct 102 ms 6392 KB correct
31 Correct 100 ms 6392 KB correct
32 Correct 96 ms 6352 KB correct
33 Correct 101 ms 6520 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB correct
2 Correct 8 ms 6272 KB correct
3 Correct 8 ms 6272 KB correct
4 Correct 8 ms 6272 KB correct
5 Correct 8 ms 6272 KB correct
6 Correct 8 ms 6272 KB correct
7 Correct 8 ms 6272 KB correct
8 Correct 8 ms 6272 KB correct
9 Correct 8 ms 6272 KB correct
10 Correct 8 ms 6272 KB correct
11 Correct 9 ms 6272 KB correct
12 Correct 8 ms 6272 KB correct
13 Correct 8 ms 6272 KB correct
14 Correct 184 ms 6708 KB correct
15 Correct 182 ms 6648 KB correct
16 Correct 197 ms 6648 KB correct
17 Correct 159 ms 6648 KB correct
18 Correct 58 ms 6392 KB correct
19 Correct 159 ms 6520 KB correct
20 Correct 148 ms 6520 KB correct
21 Correct 146 ms 6520 KB correct
22 Correct 81 ms 6520 KB correct
23 Correct 63 ms 6392 KB correct
24 Correct 54 ms 6392 KB correct
25 Correct 9 ms 6272 KB correct
26 Correct 53 ms 6272 KB correct
27 Correct 60 ms 6272 KB correct
28 Correct 18 ms 6272 KB correct
29 Correct 12 ms 6272 KB correct
30 Correct 102 ms 6392 KB correct
31 Correct 100 ms 6392 KB correct
32 Correct 96 ms 6352 KB correct
33 Correct 101 ms 6520 KB correct
34 Incorrect 424 ms 8056 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB correct
2 Correct 9 ms 6272 KB correct
3 Incorrect 244 ms 10232 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB correct
2 Correct 8 ms 6272 KB correct
3 Correct 8 ms 6272 KB correct
4 Correct 8 ms 6272 KB correct
5 Correct 8 ms 6272 KB correct
6 Correct 8 ms 6272 KB correct
7 Correct 8 ms 6272 KB correct
8 Correct 8 ms 6272 KB correct
9 Correct 8 ms 6272 KB correct
10 Correct 8 ms 6272 KB correct
11 Correct 9 ms 6272 KB correct
12 Correct 8 ms 6272 KB correct
13 Correct 8 ms 6272 KB correct
14 Correct 184 ms 6708 KB correct
15 Correct 182 ms 6648 KB correct
16 Correct 197 ms 6648 KB correct
17 Correct 159 ms 6648 KB correct
18 Correct 58 ms 6392 KB correct
19 Correct 159 ms 6520 KB correct
20 Correct 148 ms 6520 KB correct
21 Correct 146 ms 6520 KB correct
22 Correct 81 ms 6520 KB correct
23 Correct 63 ms 6392 KB correct
24 Correct 54 ms 6392 KB correct
25 Correct 9 ms 6272 KB correct
26 Correct 53 ms 6272 KB correct
27 Correct 60 ms 6272 KB correct
28 Correct 18 ms 6272 KB correct
29 Correct 12 ms 6272 KB correct
30 Correct 102 ms 6392 KB correct
31 Correct 100 ms 6392 KB correct
32 Correct 96 ms 6352 KB correct
33 Correct 101 ms 6520 KB correct
34 Incorrect 424 ms 8056 KB WA in grader: NO
35 Halted 0 ms 0 KB -