Submission #1155981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155981		12345678	Simurgh (IOI17_simurgh)	C++20	0 / 100	0 ms	324 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int vs[nx], cnt, mx;
vector<pair<int, int>> d[nx];
vector<int> g[nx], mn, qrs, vl, res;
set<int> s;

void dfs(int u, int st)
{
    vs[u]=1;
    for (auto [v, idx]:d[u])
    {
        if (vs[v]) continue;
        if (v==st) g[cnt].push_back(idx);
        else mn.push_back(idx), dfs(v, st);
    }
}

std::vector<int> find_roads(int n, std::vector<int> _u, std::vector<int> _v) {
	for (int i=0; i<_u.size(); i++) d[_u[i]].push_back({_v[i], i}), d[_v[i]].push_back({_u[i], i});
    for (int i=0; i<n; i++)
    {
        cnt=0;
        mn.clear();
        for (int j=0; j<n; j++) vs[j]=0;
        for (int j=0; j<n; j++)
        {
            if (j==i||vs[j]) continue;
            dfs(j, i);
            cnt++;
        }
        for (int j=0; j<cnt; j++)
        {
            mx=0;
            qrs=mn;
            for (int k=0; k<cnt; k++) if (k!=j) qrs.push_back(g[k][0]);
            vl.resize(g[j].size());
            for (int k=0; k<g[j].size(); k++)
            {
                qrs.push_back(g[j][k]);
                /*
                cout<<"query : ";
                for (auto x:qrs) cout<<x<<' ';
                cout<<'\n';
                */
                if (qrs.size()!=n-1) cout<<1/0;
                vl[k]=count_common_roads(qrs);
                qrs.pop_back();
                mx=max(mx, vl[k]);
            }
            for (int k=0; k<g[j].size(); k++) if (vl[k]==mx) s.insert(g[j][k]);
        }
    }
    for (auto x:s) res.push_back(x); //cout<<"x "<<x<<'\n'; 
    return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:51:45: warning: division by zero [-Wdiv-by-zero]
   51 |                 if (qrs.size()!=n-1) cout<<1/0;
      |                                            ~^~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30