oj.uz

Submission #577502

# Submission time Handle Problem Language Result Execution time Memory
577502 2022-06-14T22:26:03 Z definitelynotmee Simurgh (IOI17_simurgh) C++
0 / 100
 97 ms 4080 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e7;

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    int m = u.size();
    
    matrix<pii> g(n);
    for(int i = 0; i < m; i++){
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }

    vector<int> royal, dfstree;
    dfstree.reserve(n);
    royal.reserve(n);

    vector<int> check(n), tin(n);
    int timer = -1;

    auto gettree =[&](int id, auto dfs)->void{
        check[id] = 1;
        tin[id] = ++timer;
        for(auto [viz,edge] : g[id]){
            if(!check[viz]){
                dfstree.push_back(edge);
                dfs(viz,dfs);
            }
        }
    };

    gettree(0,gettree);
    // for(int i : dfstree){
    //     cout << "->" << u[i] << ' ' << v[i] << '\n';
    // }
    fill(all(check),0);

    auto test =[&](int id, int remove){
        vector<int> query = dfstree;
        for(int& i : query){
            if(i == remove){
                i = id;
                break;
            }
        }
        return count_common_roads(query);

    };

    auto dfs =[&](int id, int last, auto dfs)->pii{
        check[id] = 1;
        pii back = {INF,0};
        for(auto [viz,edge] : g[id]){
            if(!check[viz]){
                back = min(back,dfs(viz,edge,dfs));
            }
        }
        if(last == -1)
            return {0,0};

        int resp = back.ff == INF ? 0 : test(back.ss,last);
        vector<int> child(g[id].size());

        for(int i = 0; i < g[id].size(); i++){
            int viz = g[id][i].ff, edge = g[id][i].ss;
            if(tin[viz] > tin[id])
                continue;
            child[i] = test(edge,last);
            resp = max(resp,child[i]);
        }

        for(int i = 0; i < g[id].size(); i++){
            int viz = g[id][i].ff, edge = g[id][i].ss;
            if(tin[viz] > tin[id])
                continue;
            if(child[i] == resp){
                back = min(back,{tin[viz],edge});
                royal.push_back(edge);
            }
        }
        return back;
    };
    dfs(0,-1,dfs);

    return royal;
}

Compilation message

simurgh.cpp: In lambda function:
simurgh.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for(auto [viz,edge] : g[id]){
      |                  ^
simurgh.cpp: In lambda function:
simurgh.cpp:62:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         for(auto [viz,edge] : g[id]){
      |                  ^
simurgh.cpp: In instantiation of 'find_roads(int, std::vector<int>, std::vector<int>)::<lambda(int, int, auto:2)> [with auto:2 = find_roads(int, std::vector<int>, std::vector<int>)::<lambda(int, int, auto:2)>; pii = std::pair<int, int>]':
simurgh.cpp:92:17:   required from here
simurgh.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < g[id].size(); i++){
      |                        ~~^~~~~~~~~~~~~~
simurgh.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int i = 0; i < g[id].size(); i++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 97 ms 4080 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -