oj.uz

답안 #839319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839319 2023-08-29T16:58:54 Z andrei_boaca 열쇠 (IOI21_keys) C++17
0 / 100
 7 ms 14420 KB 
#include <vector>
#include <bits/stdc++.h>
#include "keys.h"
//#include "grader.cpp"
using namespace std;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
typedef pair<int,int> pii;
int cnt[300005],use[300005],fin[300005],have[300005],my[300005];
set<int> setik;
vector<pii> muchii[300005];
vector<pii> block[300005];
queue<int> coada;
vector<int> inblock;
void plsclean()
{
    for(int i:inblock)
        block[i].clear();
    inblock.clear();
}
int bfs(int x)
{
    int rez=0;
    coada.push(x);
    vector<int> viz;
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        if(use[nod]==x+1)
            continue;
        viz.push_back(nod);
        rez++;
        use[nod]=x+1;
        int c=my[nod];
        if(have[c]!=x+1)
        {
            have[c]=x+1;
            for(pii i:block[c])
            {
                int a=i.first;
                int b=i.second;
                if(use[a]==x+1)
                    swap(a,b);
                if(use[a]!=x+1)
                {
                    if(fin[a])
                        return 1e6;
                    coada.push(a);
                }
            }
            block[c].clear();
        }
        for(pii i:muchii[nod])
        {
            int a=i.first;
            int need=i.second;
            if(use[a]==x+1)
                continue;
            if(have[need]==x+1)
            {
                if(fin[a])
                    return 1e6;
                coada.push(a);
            }
            else
            {
                block[need].push_back({a,nod});
                inblock.push_back(need);
            }
        }
    }
    for(int i:viz)
        cnt[i]=min(cnt[i],rez);
    return rez;
}
int n,minim=1e9;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 0);
    n=r.size();
	vector<int> ord;
    for(int i=0;i<n;i++)
    {
        my[i]=r[i];
        cnt[i]=1e6;
        ord.push_back(i);
    }
    for(int i=0;i<u.size();i++)
    {
        int a=u[i];
        int b=v[i];
        int cheie=c[i];
        muchii[a].push_back({b,cheie});
        muchii[b].push_back({a,cheie});
    }
    shuffle(ord.begin(),ord.end(),rng);
    for(int i:ord)
        if(!fin[i])
        {
            cnt[i]=min(cnt[i],bfs(i));
            plsclean();
            minim=min(minim,cnt[i]);
            fin[i]=1;
        }
    for(int i=0;i<n;i++)
        if(cnt[i]==minim)
            ans[i]=1;
	return ans;
}

Compilation message

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
keys.cpp:104:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  104 |     for(int i=0;i<n;i++)
      |     ^~~
keys.cpp:107:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  107 |  return ans;
      |  ^~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14348 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Incorrect 7 ms 14392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14348 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Incorrect 7 ms 14392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14348 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Incorrect 7 ms 14392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14348 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Incorrect 7 ms 14392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14348 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Incorrect 7 ms 14392 KB Output isn't correct
5 Halted 0 ms 0 KB -