Submission #426911

#	Time	Username	Problem	Language	Result	Execution time	Memory
426911		Runtime_error_	Simurgh (IOI17_simurgh)	C++14	0 / 100	7 ms	9692 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
using namespace std;
const int inf = 2e5+9;
vector<int> cur,adj[inf],cp[inf],ask,ret;
int n,m,u[inf],v[inf],par[inf];
set<int> rets;

int root(int x){
    if(par[x] == x)
        return x;
    return par[x] = root(par[x]);
}

bool join(int x,int y){
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;
    if(rand()%2)
        swap(x,y);
    par[x] = y;
    return 1;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {

    n = N;
    m = U.size();
    for(int i=0;i<m;i++)
        u[i] = U[i],v[i] = V[i],
        adj[u[i]].pb(v[i]),adj[v[i]].pb(u[i]);

    for(int i=0;i<n;i++){
        ask.clear();
        set<int> roots;
        for(int j=0;j<n;j++)
            par[j] = j,cp[i].clear();
        for(int j=0;j<m;j++)
            if(u[j] != i && v[j] != i && join(u[j],v[j]))
                ask.pb(j);
        for(int j=0;j<m;j++){
            if(u[j] != i && v[j] != i)
                continue;
            int y = (u[j] ==i?v[j]:u[j]);
            y = root(y);
            roots.insert(y);
            cp[y].pb(j);
        }
        for(auto rt:roots){
            for(auto ort:roots)
                if(rt != ort)
                    ask.pb(cp[ort][0]);
            pi ans= pi(0,0);
            for(auto o:cp[rt]){
                ask.pb(o);
                ans = max(ans,pi(count_common_roads(ask),o));
                ask.pop_back();
            }
            for(auto ort:roots)
                if(rt != ort)
                    ask.pop_back();
           rets.insert(ans.second);
        }
    }
    for(auto o:rets)
        ret.pb(o);
    return ret;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

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