Submission #73391

#	Time	Username	Problem	Language	Result	Execution time	Memory
73391		mr_banana	Simurgh (IOI17_simurgh)	C++17	51 / 100	349 ms	6152 KiB

simurgh

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

using namespace std;
const int MN=1e5+100;
vector<int> adj[MN];
int from[MN],to[MN];
int par[MN],h[MN];
bool mark[MN];
set<int> e;
int n,m;
int vaz[MN];
void dfs(int v){
    mark[v]=1;
    for(int e1:adj[v]){
        int u=from[e1]^to[e1]^v;
        if(!mark[u]){
            par[u]=e1;
            e.insert(e1);
            h[u]=h[v]+1;
            dfs(u);
        }
    }
}
int get(){
    vector<int> ask;
    for(int i:e){
        ask.push_back(i);
    }
    return count_common_roads(ask);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
    n=N,m=u.size();
    for(int i=0;i<m;i++){
        from[i]=u[i];
        to[i]=v[i];
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    dfs(0);
    memset(vaz,-1,sizeof vaz);
    int base=get();
    for(int i=0;i<m;i++){
        if(e.count(i)==0){
            vector<int> path;
            vector<int> pans;
            int u1=from[i],v1=to[i];
            if(h[u1]<h[v1]){
                swap(u1,v1);
            }
            for(int i=h[u1]-h[v1];i>0;i--){
                path.push_back(par[u1]);
                u1=from[par[u1]]^to[par[u1]]^u1;
            }
            while(u1!=v1){
                path.push_back(par[u1]);
                u1=from[par[u1]]^to[par[u1]]^u1;
                path.push_back(par[v1]);
                v1=from[par[v1]]^to[par[v1]]^v1;
            }
            for(int j=0;j<path.size();j++){
                if((vaz[path[j]]!=-1 && vaz[i]==-1)){
                    e.erase(path[j]);
                    e.insert(i);
                    int x=get();
                    e.insert(path[j]);
                    e.erase(i);
                    if(x<base){
                        vaz[i]=0;
                    }
                    else if(x>base){
                        vaz[i]=1;
                    }
                    else{
                        vaz[i]=vaz[path[j]];
                    }
                    pans.push_back(0);
                }
                else if(vaz[path[j]]==-1){
                    e.erase(path[j]);
                    e.insert(i);
                    int x=get();
                    e.insert(path[j]);
                    e.erase(i);
                    if(x<base){
                        vaz[i]=0;
                        vaz[path[j]]=1;
                        pans.push_back(0);
                    }
                    else if(x>base){
                        vaz[i]=1;
                        vaz[path[j]]=0;
                        pans.push_back(0);
                    }
                    else{
                        pans.push_back(1);
                    }
                }
                else{
                    pans.push_back(0);
                }
            }
            if(vaz[i]==-1){
                vaz[i]=0;
            }
            for(int j=0;j<path.size();j++){
                if(pans[j]==1){
                    vaz[path[j]]=vaz[i];
                }
            }
        }
    }
    vector<int> ans;
    for(int i=0;i<m;i++){
        if(vaz[i]!=0){
            ans.push_back(i);
        }
    }
    return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:61:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<path.size();j++){
                         ~^~~~~~~~~~~~
simurgh.cpp:106:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<path.size();j++){
                         ~^~~~~~~~~~~~

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