Submission #923890

#	Time	Username	Problem	Language	Result	Execution time	Memory
923890		byunjaewoo	Simurgh (IOI17_simurgh)	C++17	51 / 100	81 ms	4584 KiB

simurgh

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

const int Nmax=510, Kmax=Nmax*Nmax/2;
int N, M, p, u[Kmax], v[Kmax], par[Nmax], parc[Nmax], dep[Nmax], dfsn[Nmax], top[Nmax], low[Nmax], back[Nmax];
int total, chk[Kmax];
vector<pair<int, int>> adj[Nmax], adj2[Nmax];
vector<tuple<int, int, int>> tree;
vector<int> V;

int value(int x, int y) {
	for(int &i:V) if(i==x) i=y;
	int ret=count_common_roads(V);
	for(int &i:V) if(i==y) i=x;
	return ret;
}

int value2(vector<int> X) {
	for(int i:X) {
		if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]);
		for(int &j:V) if(j==parc[u[i]]) j=i;
	}
	int ret=count_common_roads(V)-total;
	for(int i:X) {
		for(int &j:V) if(j==i) j=parc[u[i]], ret+=chk[parc[u[i]]];
	}
	return ret;
}

void DFS(int curr, int prev) {
	dfsn[curr]=top[curr]=++p;
	for(auto [next, c]:adj[curr]) if(next!=prev) {
		if(dfsn[next]) {
			if(top[curr]>dfsn[next]) top[curr]=dfsn[next], back[curr]=c, low[curr]=curr;
		}
		else {
			par[next]=curr, parc[next]=c, dep[next]=dep[curr]+1;
			tree.push_back({curr, next, c});
			adj2[curr].push_back({next, c});
			DFS(next, curr);
			if(top[curr]>top[next]) top[curr]=top[next], back[curr]=back[next], low[curr]=low[next];
		}
	}
}

void DFS2(int curr) {
	for(auto [next, c]:adj2[curr]) {
		DFS2(next);
		if(chk[c]!=-1) continue;
		if(top[next]>dfsn[curr]) chk[c]=1;
		else {
			vector<int> tmp;
			bool flag=false; int q=0;
			for(int i=low[next]; dfsn[i]!=top[next]; i=par[i]) {
				tmp.push_back(parc[i]);
				if(chk[parc[i]]!=-1) flag=true, q=parc[i];
			}
			if(flag) {
				chk[back[next]]=chk[q]+value(q, back[next])-total;
				for(int i:tmp) if(chk[i]==-1) chk[i]=chk[back[next]]-value(i, back[next])+total;
			}
			else {
				int X=total;
				vector<int> Y;
				for(int i:tmp) Y.push_back(value(i, back[next]));
				bool flag2=false;
				for(int i=0; i<Y.size(); i++) {
					if(Y[i]==X+1) flag2=true, chk[back[next]]=1, chk[tmp[i]]=0;
					else if(Y[i]==X-1) flag2=true, chk[back[next]]=0, chk[tmp[i]]=1;
				}
				if(flag2) {
					for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
				}
				else {
					chk[back[next]]=false;
					for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
				}
			}
		}
	}
}

void F(int l, int r, int sum, vector<int> E) {
	if(l==r) {
		if(sum) chk[E[l]]=1;
		else chk[E[r]]=0;
		return;
	}
	if(l>r) return;
	int m=(l+r)/2;
	vector<int> tmp;
	for(int i=l; i<=m; i++) tmp.push_back(E[i]);
	int lsum=value2(tmp);
	if(lsum) F(l, m, lsum, E);
	if(sum-lsum) F(m+1, r, sum-lsum, E);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::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]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
	}
	for(int i=0; i<M; i++) chk[i]=-1;
	DFS(0, -1);
	for(auto [u, v, c]:tree) V.push_back(c);
	total=count_common_roads(V);
	DFS2(0);
	for(int i=0; i<N; i++) {
		vector<int> E;
		for(auto [j, c]:adj[i]) if(dfsn[j]>dfsn[i] && !chk[c]) E.push_back(c);
		if(!E.empty()) F(0, E.size()-1, value2(E), E);
	}
	for(int i=0; i<M; i++) if(chk[i]==-1) {
		if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]);
		chk[i]=chk[parc[u[i]]]+value(parc[u[i]], i)-total;
	}
	vector<int> ret;
	for(int i=0; i<M; i++) if(chk[i]==1) ret.push_back(i);
	return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'void DFS2(int)':
simurgh.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0; i<Y.size(); i++) {
      |                  ~^~~~~~~~~
simurgh.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |      for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
      |                   ~^~~~~~~~~
simurgh.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |      for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
      |                   ~^~~~~~~~~

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