oj.uz

답안 #790660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790660 2023-07-23T04:49:54 Z PoonYaPat Simurgh (IOI17_simurgh) C++14
0 / 100
 114 ms 5296 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

struct Edge {
	int a,idx,mode;
};

int n,m,deg[505];
vector<pii> edge;
priority_queue<pii> pq; //deg, node
vector<Edge> adj[505];
bool fin[505],ans[250010];

int p[505],r[505];

void reset() {
	for (int i=0; i<n; ++i) p[i]=i, r[i]=1;
}

int find(int x) {
	while (x!=p[x]) x=p[x];
	return x; 
} 

void unite(int x, int y) {
	x=find(x); y=find(y);
	if (r[x]<r[y]) swap(x,y);
	p[y]=x;
	if (r[x]==r[y]) ++r[x];
}

void solve1(int x) {
	vector<pii> temp; //val,idx
	vector<int> v;
	int ma=0;
	reset();

	for (int i=0; i<m; ++i) {
		if (edge[i].first==x || edge[i].second==x) continue;
		if (find(edge[i].first)!=find(edge[i].second)) {
			unite(edge[i].first,edge[i].second);
			v.push_back(i);
		}
	}

	for (auto s : adj[x]) {
		v.push_back(s.idx);
		int h=count_common_roads(v);
		ma=max(h,ma);
		temp.push_back(pii(h,s.idx));
		v.pop_back();
	}

	for (auto s : temp) if (s.first==ma) ans[s.second]=true;
}


vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n=N;
	m=u.size();
	for (int i=0; i<m; ++i) {
		edge.push_back(pii(u[i],v[i]));
		adj[u[i]].push_back({v[i],i,-1});
		adj[v[i]].push_back({u[i],i,-1});
		++deg[u[i]];
		++deg[v[i]];
	}

	int ma=0, st;
	for (int i=0; i<n; ++i) if (deg[i]>ma) ma=deg[i], st=i;

	for (int i=0; i<n; ++i) solve1(i);
	vector<int> Ans;
	for (int i=0; i<m; ++i) if (ans[i]) Ans.push_back(i);
	return Ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:12: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   71 |  int ma=0, st;
      |            ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Incorrect 0 ms 212 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Incorrect 0 ms 212 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Incorrect 0 ms 212 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 114 ms 5296 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Incorrect 0 ms 212 KB WA in grader: NO
10 Halted 0 ms 0 KB -