제출 #1366117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366117		mariza	Simurgh (IOI17_simurgh)	C++20	30 / 100	303 ms	1868 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=500;

struct DSU{
    ll p[N];

    void init(ll n){
        for(ll i=0; i<n; i++){
            p[i]=i;
        }
    }

    ll find(ll u){
        if(p[u]==u) return u;
        else return p[u]=find(p[u]);
    }

    void merge(ll u, ll v){
        u=find(u);
        v=find(v);

        if(u==v) return;
        p[u]=v;
    }
};

vector<pair<ll,ll>> t[N];

ll par[N];
void dfs1(ll curr, ll prev){
    for(auto nxt:t[curr]){
        if(nxt.first==prev) continue;
        par[nxt.first]=nxt.second;
        dfs1(nxt.first,curr);
    }
}

vector<ll> p;
bool dfs(ll curr, ll prev, ll x){
    if(curr==x) return 1;

    for(auto nxt:t[curr]){
        if(nxt.first==prev) continue;
        if(dfs(nxt.first,curr,x)){
            p.push_back(nxt.second);
            return 1;
        }
    }
    return 0;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v){
    ll m=u.size();

    DSU dsu;
    dsu.init(n);

    bool x[m]={}; 
    vector<int> r;
    for(ll i=0; i<m; i++){
        if(dsu.find(u[i])!=dsu.find(v[i])){
            t[u[i]].push_back({v[i],i});
            t[v[i]].push_back({u[i],i});
            dsu.merge(u[i],v[i]);
            x[i]=1;
            r.push_back(i);
        }
    }

    ll ans1=count_common_roads(r);
    par[0]=-1;
    dfs1(0,0);

    bool y[m];
    for(ll i=0; i<m; i++) y[i]=x[i];

    for(ll i=0; i<m; i++){
        if(x[i]) continue;

        p.clear();
        dfs(u[i],u[i],v[i]);

        for(auto j:p){
            r.clear();
            for(ll k=0; k<m; k++){
                if(x[k] && k!=j) r.push_back(k);
            }
            r.push_back(i);

            if(count_common_roads(r)>ans1){
                y[i]=1;
                y[j]=0;
            }
        }
    }

    vector<int> ans;
    for(ll i=0; i<m; i++){
        if(y[i]){
            ans.push_back(i);
            // cout<<i<<" ";
        }
    }
    // cout<<endl;
    return ans;
}

• 서브태스크 1: 13 / 13
• 서브태스크 2: 17 / 17
• 서브태스크 3: 0 / 21
• 서브태스크 4: 0 / 19
• 서브태스크 5: 0 / 30