oj.uz

답안 #1113382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113382 2024-11-16T13:55:16 Z epicci23 Simurgh (IOI17_simurgh) C++17
30 / 100
 140 ms 3528 KB 
#include "bits/stdc++.h"
#include "simurgh.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
 
const int N = 505;
 
struct DSU{
  vector<int> par,siz;
  stack<array<int,2>> st;
  DSU(int _n){
    siz.assign(_n,1);
    par.assign(_n,0);
    iota(all(par),0);
  }
  int find(int a){
    if(par[a]==a) return a;
    return find(par[a]);
  }
  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    st.push({a,b});
    par[a]=b;
    siz[b]+=siz[a];
  }
  void rollback(){
  	if(st.empty()) return;
  	auto x = st.top();
  	st.pop();
    par[x[0]] = x[0];
    siz[x[1]] -= siz[x[0]];
  }
};
 
vector<array<int,2>> edges;
vector<int> kader;
int n,m;
 
bool check(int a){
  vector<int> vis(m, 0);
 
  if(kader[a] == -1) return 0;
  if(kader[a] == 1) return 1;
  if(count(all(kader),1) == n - 1) return 0;
  
  vector<int> span;
  DSU dsu(n),dsu2(n);
 
  for(int x = 0; x < m ; x++){
  	if(kader[x] != 1) continue;
  	span.push_back(x);
  	vis[x] = 1;
  	dsu.unite(edges[x][0],edges[x][1]);
  	dsu2.unite(edges[x][0],edges[x][1]);
  }
 
  if(dsu.find(edges[a][0])==dsu.find(edges[a][1])) return 0;
  dsu.unite(edges[a][0],edges[a][1]);
  int sil = sz(span);
  vis[a] = 1;
  span.push_back(a);
 
  for(int i = a + 1; i < m ; i++){
  	if(dsu.find(edges[i][0]) == dsu.find(edges[i][1])) continue;
  	dsu.unite(edges[i][0],edges[i][1]);
  	dsu2.unite(edges[i][0],edges[i][1]);
  	vis[i] = 1;
    span.push_back(i);
  }
 
  int kaydet = count_common_roads(span);
  span.erase(span.begin()+sil);
 
  vector<int> same;
  same.push_back(a);
 
  for(int i = a + 1; i < m ; i++){
  	if(vis[i]) continue;
    if(dsu2.find(edges[i][0]) == dsu2.find(edges[i][1])) continue;
    dsu2.unite(edges[i][0],edges[i][1]);
    span.push_back(i);
    int kaydet2 = count_common_roads(span);
    if(kaydet2 == kaydet + 1){
    	for(int U : same) kader[U] = -1;
    	kader[i] = 1;
    	return 0;
    }
    else if(kaydet2 == kaydet - 1){
    	for(int U : same) kader[U] = 1;
    	kader[i] = -1;
    	return 1;
    }
    else same.push_back(i);
    span.pop_back();
    dsu2.rollback();
  }
   
  for(int U : same) kader[U] = 1;
  return 1;
}
 
vector<int> find_roads(int _n, vector<int> u, vector<int> v){
  m = sz(u), n = _n;
  kader.assign(m, 0);
  for(int i=0;i<m;i++) edges.push_back({u[i],v[i]});
  for(int i=0;i<m;i++) check(i);
  vector<int> ans;
  for(int i=0;i<m;i++) if(kader[i]==1) ans.push_back(i);
  return ans;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB correct
2 Correct 1 ms 336 KB correct
3 Correct 1 ms 336 KB correct
4 Correct 1 ms 336 KB correct
5 Correct 1 ms 336 KB correct
6 Correct 1 ms 336 KB correct
7 Correct 1 ms 508 KB correct
8 Correct 1 ms 336 KB correct
9 Correct 1 ms 336 KB correct
10 Correct 1 ms 336 KB correct
11 Correct 1 ms 336 KB correct
12 Correct 1 ms 336 KB correct
13 Correct 1 ms 336 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB correct
2 Correct 1 ms 336 KB correct
3 Correct 1 ms 336 KB correct
4 Correct 1 ms 336 KB correct
5 Correct 1 ms 336 KB correct
6 Correct 1 ms 336 KB correct
7 Correct 1 ms 508 KB correct
8 Correct 1 ms 336 KB correct
9 Correct 1 ms 336 KB correct
10 Correct 1 ms 336 KB correct
11 Correct 1 ms 336 KB correct
12 Correct 1 ms 336 KB correct
13 Correct 1 ms 336 KB correct
14 Correct 4 ms 336 KB correct
15 Correct 4 ms 336 KB correct
16 Correct 3 ms 336 KB correct
17 Correct 4 ms 336 KB correct
18 Correct 2 ms 336 KB correct
19 Correct 5 ms 336 KB correct
20 Correct 3 ms 336 KB correct
21 Correct 4 ms 336 KB correct
22 Correct 2 ms 336 KB correct
23 Correct 2 ms 504 KB correct
24 Correct 3 ms 336 KB correct
25 Correct 1 ms 336 KB correct
26 Correct 2 ms 336 KB correct
27 Correct 2 ms 336 KB correct
28 Correct 2 ms 336 KB correct
29 Correct 1 ms 336 KB correct
30 Correct 2 ms 336 KB correct
31 Correct 2 ms 336 KB correct
32 Correct 2 ms 336 KB correct
33 Correct 2 ms 336 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB correct
2 Correct 1 ms 336 KB correct
3 Correct 1 ms 336 KB correct
4 Correct 1 ms 336 KB correct
5 Correct 1 ms 336 KB correct
6 Correct 1 ms 336 KB correct
7 Correct 1 ms 508 KB correct
8 Correct 1 ms 336 KB correct
9 Correct 1 ms 336 KB correct
10 Correct 1 ms 336 KB correct
11 Correct 1 ms 336 KB correct
12 Correct 1 ms 336 KB correct
13 Correct 1 ms 336 KB correct
14 Correct 4 ms 336 KB correct
15 Correct 4 ms 336 KB correct
16 Correct 3 ms 336 KB correct
17 Correct 4 ms 336 KB correct
18 Correct 2 ms 336 KB correct
19 Correct 5 ms 336 KB correct
20 Correct 3 ms 336 KB correct
21 Correct 4 ms 336 KB correct
22 Correct 2 ms 336 KB correct
23 Correct 2 ms 504 KB correct
24 Correct 3 ms 336 KB correct
25 Correct 1 ms 336 KB correct
26 Correct 2 ms 336 KB correct
27 Correct 2 ms 336 KB correct
28 Correct 2 ms 336 KB correct
29 Correct 1 ms 336 KB correct
30 Correct 2 ms 336 KB correct
31 Correct 2 ms 336 KB correct
32 Correct 2 ms 336 KB correct
33 Correct 2 ms 336 KB correct
34 Incorrect 140 ms 1560 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB correct
2 Correct 1 ms 336 KB correct
3 Correct 1 ms 336 KB correct
4 Correct 1 ms 336 KB correct
5 Correct 1 ms 336 KB correct
6 Correct 1 ms 336 KB correct
7 Correct 1 ms 508 KB correct
8 Correct 1 ms 336 KB correct
9 Correct 1 ms 336 KB correct
10 Correct 1 ms 336 KB correct
11 Correct 1 ms 336 KB correct
12 Correct 1 ms 336 KB correct
13 Correct 1 ms 336 KB correct
14 Correct 4 ms 336 KB correct
15 Correct 4 ms 336 KB correct
16 Correct 3 ms 336 KB correct
17 Correct 4 ms 336 KB correct
18 Correct 2 ms 336 KB correct
19 Correct 5 ms 336 KB correct
20 Correct 3 ms 336 KB correct
21 Correct 4 ms 336 KB correct
22 Correct 2 ms 336 KB correct
23 Correct 2 ms 504 KB correct
24 Correct 3 ms 336 KB correct
25 Correct 1 ms 336 KB correct
26 Correct 2 ms 336 KB correct
27 Correct 2 ms 336 KB correct
28 Correct 2 ms 336 KB correct
29 Correct 1 ms 336 KB correct
30 Correct 2 ms 336 KB correct
31 Correct 2 ms 336 KB correct
32 Correct 2 ms 336 KB correct
33 Correct 2 ms 336 KB correct
34 Incorrect 140 ms 1560 KB WA in grader: NO
35 Halted 0 ms 0 KB -