Submission #577503

#	Time	Username	Problem	Language	Result	Execution time	Memory
577503		definitelynotmee	Simurgh (IOI17_simurgh)	C++98	51 / 100	117 ms	3500 KiB

simurgh

#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 >= tin[id] ? 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 (stderr)

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: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30