Submission #1093906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093906		azberjibiou	Simurgh (IOI17_simurgh)	C++17	100 / 100	110 ms	8388 KiB

simurgh

#include "simurgh.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=505;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct uf{
    int p[mxN];
    void init(int n){for(int i=0;i<n;i++) p[i]=i;}
    int fp(int a){return p[a]==a ? a : p[a]=fp(p[a]);}
    void mrg(int a, int b){p[fp(a)]=fp(b);}
};
int N;
vector <int> v[mxN];
vector <pii> E;
int num[mxN][mxN];
int gold[mxN][mxN];
//dfs
bool Chk[mxN];
int dep[mxN], par[mxN];
vector <int> sub[mxN];
vector <int> tree;
void init(){
    for(int i=0;i<mxN;i++) v[i].clear();
    E.clear();
    for(int i=0;i<mxN;i++) for(int j=0;j<mxN;j++) num[i][j]=-1, gold[i][j]=-1;
    for(int i=0;i<mxN;i++) Chk[i]=false, dep[i]=0, par[i]=0, sub[i].clear();
    tree.clear();
}
void dfs(int now){
    Chk[now]=true;
    sub[now].push_back(now);
    for(int nxt : v[now]) if(!Chk[nxt]){
        dep[nxt]=dep[now]+1;
        par[nxt]=now;
        tree.push_back(num[nxt][now]);
        dfs(nxt);
        for(int x : sub[nxt]) sub[now].push_back(x);
    }
}
uf U_qry;
int make_query(vector <int> qry, bool proc){ // qry does not have a cycle!, proc: remove value of edges out of qry
    vector <int> res=qry;
    U_qry.init(N);
    for(int x : qry) U_qry.mrg(E[x].fi, E[x].se);
    for(int x : tree){
        auto [now1, now2]=E[x];
        if(U_qry.fp(now1)!=U_qry.fp(now2)){
            res.push_back(x);
            U_qry.mrg(now1, now2);
        }
    }
    int val=count_common_roads(res);
    if(proc){
        for(int i=qry.size();i<res.size();i++){
            auto [now1, now2]=E[res[i]];
            if(gold[now1][now2]==1) val--;
        }
    }
    return val;
}
vector <int> minu(vector <int> gph, int x){
    vector <int> res;
    for(int y : gph) if(y!=x) res.push_back(y);
    return res;
}
void check_cycle(vector <int> cyc){
    vector <int> qres(cyc.size(), -1);
    for(int i=0;i<cyc.size();i++){
        auto [now1, now2]=E[cyc[i]];
        if(gold[now1][now2]==-1) qres[i]=make_query(minu(cyc, cyc[i]), false);
    }
    int know=-1, tot=-1;
    for(int x : cyc) if(gold[E[x].fi][E[x].se]!=-1) know=x;
    if(know!=-1){
        tot=make_query(minu(cyc, know), false)+gold[E[know].fi][E[know].se];
    }
    else {
        int maxi=-1, mini=1'000'000;
        for(int i=0;i<cyc.size();i++) maxi=max(maxi, qres[i]), mini=min(mini, qres[i]);
        bool same=(maxi==mini);
        if(same) tot=maxi;
        else{
            int sum=0;
            for(int i=0;i<cyc.size();i++) sum+=qres[i];
            tot=sum/cyc.size()+1;
        }
    }
    for(int i=0;i<cyc.size();i++){
        auto [now1, now2]=E[cyc[i]];
        if(gold[now1][now2]==-1){
            if(qres[i]==tot) gold[now1][now2]=gold[now2][now1]=0;
            else gold[now1][now2]=gold[now2][now1]=1;
        }
    }
}void make_spanning_tree(){
    dfs(0);
    for(int ednum : tree){
        auto [now1, now2]=E[ednum];
        if(dep[now1]>dep[now2]) swap(now1, now2);
        if(gold[now1][now2]!=-1) continue;
        int down=-1, up=-1;
        for(int x : sub[now2]) for(int y : v[x]) if(dep[y]<=dep[now1] && (x!=now2 || y!=now1)) down=x, up=y;
        if(up==-1){
            gold[now1][now2]=gold[now2][now1]=1;
            continue;
        }
        vector <int> cyc;
        int pnt=down;
        while(pnt!=up){
            cyc.push_back(num[pnt][par[pnt]]);
            pnt=par[pnt];
        }
        cyc.push_back(num[down][up]);
        check_cycle(cyc);
    }
}
vector <int> rng(vector <int> s, pii lr){
    vector <int> res;
    for(int i=lr.fi;i<=lr.se;i++) res.push_back(s[i]);
    return res;
}
void find_gold(){
    for(int i=0;i<N;i++){
        vector <int> ct;
        for(int j=i+1;j<N;j++){
            if(num[i][j]!=-1 && gold[i][j]==-1) ct.push_back(num[i][j]);
        }
        while(ct.size() && make_query(ct, true)!=0){
            int s=0, e=ct.size()-1;
            while(s!=e){
                int mid=(s+e)/2;
                if(make_query(rng(ct, pii(s, mid)), true)==0) s=mid+1;
                else e=mid;
            }
            auto [now1, now2]=E[ct[s]];
            gold[now1][now2]=gold[now2][now1]=1;
            ct=minu(ct, ct[s]);
        }
    }
}
std::vector<int> find_roads(int n, std::vector<int> a, std::vector<int> b) {
    N=n;
    init();
    for(int i=0;i<a.size();i++){
        int t1=a[i], t2=b[i];
        v[t1].push_back(t2);
        v[t2].push_back(t1);
        E.emplace_back(t1, t2);
        num[t1][t2]=num[t2][t1]=i;
    }
    make_spanning_tree();
    find_gold();
	vector<int> r;
    for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) if(gold[i][j]==1) r.push_back(num[i][j]);
    return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'int make_query(std::vector<int>, bool)':
simurgh.cpp:67:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=qry.size();i<res.size();i++){
      |                              ~^~~~~~~~~~~
simurgh.cpp: In function 'void check_cycle(std::vector<int>)':
simurgh.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<cyc.size();i++){
      |                 ~^~~~~~~~~~~
simurgh.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int i=0;i<cyc.size();i++) maxi=max(maxi, qres[i]), mini=min(mini, qres[i]);
      |                     ~^~~~~~~~~~~
simurgh.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(int i=0;i<cyc.size();i++) sum+=qres[i];
      |                         ~^~~~~~~~~~~
simurgh.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<cyc.size();i++){
      |                 ~^~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:157:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~

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