oj.uz

답안 #216425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216425 2020-03-27T09:38:20 Z emil_physmath Simurgh (IOI17_simurgh) C++17
0 / 100
 24 ms 3064 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];
vector<int> dfsq;
vector<Jmp> nei[maxN];
vector<int> same[maxN];
pair<int, 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)
{
    static int time = 0;
    used[v] = true;
    in[v] = ++time;
    par[v] = p;
    fup[v] = {-1, {-1, -1}};
    for (Jmp to: nei[v])
        if (!used[to])
        {
            dfsq.push_back(to.ind);
            DFS(to, {v, to.ind});
            if (fup[v].first == -1 || (fup[to].first != -1 && in[fup[to].second] <= in[fup[v].second]))
                fup[v] = fup[to];
        }
        else if (to != p && (fup[v].first == -1 || in[to] <= in[fup[v].second]))
            fup[v] = {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();
    for (int i = 0; i < m; ++i)
        gold[i] = -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});
    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].first == -1 || in[fup[v].second] > in[u])
        {
            gold[i] = 1;
            continue;
        }
        int dfse, backe;
        if (par[v] == u)
            dfse = i, backe = fup[v].second.ind;
        else
            backe = i, dfse = par[v].ind;
        auto it = find(dfsq.begin(), dfsq.end(), dfse);
        *it = 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;
        *it = dfse;
    }
    for (int i = 0; i < m; ++i)
        if (gold[i] != -1)
            DFS1(i);
    for (int i = 0; i < m; ++i)
        if (gold[i] == -1)
            gold[i] = 0;
    vector<int> ans;
    for (int i = 0; i < m; ++i)
        if (gold[i])
            ans.push_back(i);
    return ans;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB correct
2 Correct 4 ms 384 KB correct
3 Correct 5 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 4 ms 384 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 384 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 4 ms 384 KB correct
12 Incorrect 5 ms 384 KB WA in grader: NO
13 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB correct
2 Correct 4 ms 384 KB correct
3 Correct 5 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 4 ms 384 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 384 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 4 ms 384 KB correct
12 Incorrect 5 ms 384 KB WA in grader: NO
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB correct
2 Correct 4 ms 384 KB correct
3 Correct 5 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 4 ms 384 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 384 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 4 ms 384 KB correct
12 Incorrect 5 ms 384 KB WA in grader: NO
13 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB correct
2 Correct 4 ms 384 KB correct
3 Runtime error 24 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB correct
2 Correct 4 ms 384 KB correct
3 Correct 5 ms 384 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 4 ms 384 KB correct
6 Correct 4 ms 384 KB correct
7 Correct 4 ms 384 KB correct
8 Correct 4 ms 384 KB correct
9 Correct 4 ms 384 KB correct
10 Correct 5 ms 384 KB correct
11 Correct 4 ms 384 KB correct
12 Incorrect 5 ms 384 KB WA in grader: NO
13 Halted 0 ms 0 KB -