Submission #1069338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069338		Ahmed57	Simurgh (IOI17_simurgh)	C++17	100 / 100	116 ms	34744 KiB

simurgh

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

using namespace std;
#pragma GCC optimize("Ofast")
int vis[300001];
int dep[300001];
pair<int,int> mi[300001];
pair<int,int> PR[300001];
vector<pair<int,int>> adj[300001];
vector<pair<int,int>> back[300001];
vector<pair<int,int>> tree[300001];
vector<int> tr;
vector<pair<int,int>> edg;
void dfs(int i,int pr){
    vis[i] = 1;
    dep[i] = dep[pr]+1;
    mi[i] = {-1,-1};
    for(auto j:adj[i]){
        if(vis[j.first]&&dep[j.first]<dep[i]&&j.first!=pr){
            if(mi[i].first==-1)mi[i] = {i,j.first};
            else if(dep[j.first]<dep[mi[i].second])mi[i] = {i,j.first};
            back[i].push_back(j);
			//cout<<"back:"<<i<<" "<<j.first<<endl;
        }
		if(vis[j.first])continue;
        PR[j.first] = {i,j.second};
        tree[i].push_back(j);
		//cout<<"tree:"<<i<<" "<<j.first<<" "<<j.second<<endl;
        dfs(j.first,i);
        tr.push_back(j.second);
        if(mi[i].first==-1)mi[i] = mi[j.first];
        else if(mi[j.first].first!=-1&&dep[mi[j.first].second]<dep[mi[i].second])mi[i] = mi[j.first];
    }
}
int p[300001],N;
int ans[300001];
int find(int x){
    if(x==p[x])return x;
    return p[x] = find(p[x]);
}
void mergegroup(int a,int b){
    a = find(a);b = find(b);
    if(a==b)return ;
    p[a] = b;
}
int que(vector<int> v,bool ss){
    for(int i = 0;i<N;i++){
        p[i] = i;
    }
    for(int i = 0;i<v.size();i++){
        mergegroup(edg[v[i]].first,edg[v[i]].second);
    }
    int all = 0;
    for(auto i:tr){
        if(find(edg[i].first)!=find(edg[i].second)){
            v.push_back(i);
            all+=ans[i];
            mergegroup(edg[i].first,edg[i].second);
        }
    }
    if(ss)all = count_common_roads(v)-all;
    else all = count_common_roads(v);
    return all;
}
void answer(int i){
    for(auto j:tree[i]){
        if(ans[j.second]!=-1)continue;
		//cout<<j.second<<endl;
        int lol = mi[j.first].second;
        if(lol==-1||dep[lol]>dep[i]){
            ans[j.second] = 1;
        }else{
            int st = mi[j.first].first;
			//cout<<st<<" "<<lol<<endl;
            vector<int> v;
            while(st!=lol){
                v.push_back(PR[st].second);
                st = PR[st].first;
            }

            for(auto e:back[mi[j.first].first]){
                if(e.first==lol){
                    v.push_back(e.second);
                    break;
                }
            }
			//for(auto e:v)cout<<e<<"xx ";
			//cout<<endl;
            int ma = -1;
            for(auto e:v){
                if(ans[e]==0){
                    vector<int> Q;
                    for(int w:v){
                        if(w==e)continue;
                        Q.push_back(w);
                    }
                    ma = que(Q,0);
                    break;
                }
            }
			//cout<<"ddd"<<endl;
            if(ma!=-1){
				//cout<<j.second<<"lollll"<<endl;
                for(auto e:v){
                    if(ans[e]==-1){
                        vector<int> Q;
                        for(int w:v){
                            if(w==e)continue;
                            Q.push_back(w);
                        }
                        if(ma==que(Q,0)){
                            ans[e] = 0;
                        }else ans[e] = 1;
                    }
                }   
            }else{
                set<pair<int ,int >> s;
				//cout<<"dd"<<endl;
                for(auto e:v){
                    if(ans[e]==-1){
                        vector<int> Q;
                        for(int w:v){
                            if(w==e)continue;
                            Q.push_back(w);
                        }
                        s.insert({que(Q,0),e});
                    }
                }
                int la = (*(--s.end())).first;
                int sm = (*s.begin()).first;
                if(la==sm){
                    for(auto w:s)ans[w.second] = 0;
                }else{
                    for(auto w:s){
						//cout<<w.first<<"nanan"<<w.second<<endl;
                        if(w.first==la)ans[w.second] = 0;
                        else ans[w.second] = 1;
						//cout<<w.second<<" "<<ans[w.second]<<endl;
                    }
                }
            }
        }   
    }
	for(auto j:tree[i]){answer(j.first);}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v){
	N = n;
	//cout<<"hhh"<<endl;
    for(int i = 0;i<u.size();i++){
        ans[i] = -1;
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
        edg.push_back({u[i],v[i]});
    }
    PR[0] = {-1,-1};
    dfs(0,0);
	//cout<<"hh"<<endl;
    answer(0);
	//cout<<"vvv"<<endl;
    for(int i = 0;i<n;i++){
        int la = 0;
        while(1){
            if(la==back[i].size())break;
            vector<int> Q;
            for(int e = la;e<back[i].size();e++)Q.push_back(back[i][e].second);
            if(que(Q,1)){
                int l = la , r = back[i].size()-1 , ANS = 0;
                while(l<=r){
                    int mid = (l+r)/2;
                    vector<int> Q;
                    for(int e = la;e<=mid;e++){
                        Q.push_back(back[i][e].second);
                    }
                    if(que(Q,1)){
                        ANS = mid;r = mid-1;
                    }else l = mid+1;
                }
                ans[back[i][ANS].second] = 1;
                la = ANS+1;
            }else break;
        }
    }
    vector<int> good;
    for(int i = 0;i<u.size();i++){
        if(ans[i]==1){
            good.push_back(i);
        }
    }
	//cout<<"ggg"<<endl;
	/*for(int i = 0;i<good.size();i++){
		cout<<good[i]<<"hhhh";
	}*/
    return good;
}

Compilation message (stderr)

simurgh.cpp: In function 'int que(std::vector<int>, bool)':
simurgh.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0;i<u.size();i++){
      |                   ~^~~~~~~~~
simurgh.cpp:164:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             if(la==back[i].size())break;
      |                ~~^~~~~~~~~~~~~~~~
simurgh.cpp:166:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             for(int e = la;e<back[i].size();e++)Q.push_back(back[i][e].second);
      |                            ~^~~~~~~~~~~~~~~
simurgh.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i = 0;i<u.size();i++){
      |                   ~^~~~~~~~~

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