Submission #923099

#	Time	Username	Problem	Language	Result	Execution time	Memory
923099		byunjaewoo	Simurgh (IOI17_simurgh)	C++17	0 / 100	61 ms	5212 KiB

simurgh

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

const int Nmax=510, Kmax=Nmax*Nmax/2;
int N, M, p, G[Nmax][Nmax], par[Nmax], parc[Nmax], inv[Nmax], dep[Nmax], dfsn[Nmax], top[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) {
	// cout<<"value "<<"delete "<<x<<", add "<<y<<"\n";
	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;
}

void DFS(int curr, int prev) {
	dfsn[curr]=top[curr]=++p, inv[p]=curr;
	for(auto [next, c]:adj[curr]) if(next!=prev) {
		if(dfsn[next]) {
			if(top[curr]>dfsn[next]) top[curr]=dfsn[next], back[curr]=c;
		}
		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]=c;
		}
	}
}

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=next; i!=inv[top[next]]; i=par[i]) {
				tmp.push_back(parc[i]);
				if(chk[parc[i]]!=-1) flag=true, q=parc[i];
			}
			/*cout<<"tmp ";
			for(int i:tmp) cout<<i<<" ";
			cout<<"\n";
			cout<<flag<<", "<<back[next]<<"\n";*/
			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;
				}
			}
		}
	}
}

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++) {
		adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
		G[u[i]][v[i]]=G[v[i]][u[i]]=i;
	}
	for(int i=0; i<M; i++) chk[i]=-1;
	DFS(0, -1);
	/*cout<<"tree:\n";
	for(auto [u, v, c]:tree) cout<<u<<", "<<v<<": "<<c<<"\n";
	cout<<"\n";*/
	for(auto [u, v, c]:tree) V.push_back(c);
	total=count_common_roads(V);
	DFS2(1);
	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[G[u[i]][par[u[i]]]]-total+value(G[u[i]][par[u[i]]], i);
	}
	vector<int> ret;
	for(int i=0; i<M; i++) if(chk[i]) ret.push_back(i);
	/*cout<<"ret: ";
	for(int i:ret) cout<<i<<" ";
	cout<<"\n";*/
	return ret;
}

Compilation message (stderr)

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

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