oj.uz

답안 #441550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441550 2021-07-05T11:06:10 Z azberjibiou 열쇠 (IOI21_keys) C++17
37 / 100
 3000 ms 228020 KB 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
const int mxN=300100;
int N, M;
queue <int> que;
queue <int> cque[mxN];
vector <pii> adj[mxN];
vector <int> ans;
bool Chk[mxN], CChk[mxN];
int cnt=1000000;
void unlock(int cnum)
{
    CChk[cnum]=true;
    while(!cque[cnum].empty())
    {
        int now=cque[cnum].front();
        cque[cnum].pop();
        if(Chk[now])    continue;
        Chk[now]=true;
        que.push(now);
    }
}
void push_in(int nnum, int cnum)
{
    if(CChk[cnum])
    {
        if(Chk[nnum])   return;
        Chk[nnum]=true;
        que.push(nnum);
    }
    else
    {
        cque[cnum].push(nnum);
    }
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	N=r.size();
	M=u.size();
	for(int i=0;i<M;i++)
    {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    ans.resize(N);
    for(int i=0;i<N;i++)
    {
        while(!que.empty()) que.pop();
        for(int j=0;j<N;j++)    while(!cque[j].empty()) cque[j].pop();
        for(int j=0;j<N;j++)    Chk[j]=false, CChk[j]=false;
        que.push(i);
        Chk[i]=true;
        while(!que.empty())
        {
            int now=que.front();
            que.pop();
            if(!CChk[r[now]])
            {
                unlock(r[now]);
            }
            for(pii nxt : adj[now])
            {
                if(!Chk[nxt.fir])   push_in(nxt.fir, nxt.sec);
            }
        }
        for(int j=0;j<N;j++)    if(Chk[j])  ans[i]++;
    }
    for(int i=0;i<N;i++)    cnt=min(cnt, ans[i]);
    for(int i=0;i<N;i++)    ans[i]=(ans[i]==cnt ? 1 : 0);
	return ans;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 209360 KB Output is correct
2 Correct 162 ms 209364 KB Output is correct
3 Correct 145 ms 209284 KB Output is correct
4 Correct 163 ms 209368 KB Output is correct
5 Correct 154 ms 209340 KB Output is correct
6 Correct 184 ms 209372 KB Output is correct
7 Correct 146 ms 209288 KB Output is correct
8 Correct 176 ms 209364 KB Output is correct
9 Correct 166 ms 209300 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 209360 KB Output is correct
2 Correct 162 ms 209364 KB Output is correct
3 Correct 145 ms 209284 KB Output is correct
4 Correct 163 ms 209368 KB Output is correct
5 Correct 154 ms 209340 KB Output is correct
6 Correct 184 ms 209372 KB Output is correct
7 Correct 146 ms 209288 KB Output is correct
8 Correct 176 ms 209364 KB Output is correct
9 Correct 166 ms 209300 KB Output is correct
10 Correct 153 ms 209296 KB Output is correct
11 Correct 149 ms 209372 KB Output is correct
12 Correct 152 ms 209388 KB Output is correct
13 Correct 171 ms 209476 KB Output is correct
14 Correct 152 ms 209332 KB Output is correct
15 Correct 153 ms 209304 KB Output is correct
16 Correct 146 ms 209252 KB Output is correct
17 Correct 149 ms 209356 KB Output is correct
18 Correct 163 ms 209248 KB Output is correct
19 Correct 148 ms 209348 KB Output is correct
20 Correct 155 ms 209360 KB Output is correct
21 Correct 153 ms 209388 KB Output is correct
22 Correct 145 ms 209296 KB Output is correct
23 Correct 158 ms 209316 KB Output is correct
24 Correct 152 ms 209372 KB Output is correct
25 Correct 154 ms 209268 KB Output is correct
26 Correct 155 ms 209372 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 209360 KB Output is correct
2 Correct 162 ms 209364 KB Output is correct
3 Correct 145 ms 209284 KB Output is correct
4 Correct 163 ms 209368 KB Output is correct
5 Correct 154 ms 209340 KB Output is correct
6 Correct 184 ms 209372 KB Output is correct
7 Correct 146 ms 209288 KB Output is correct
8 Correct 176 ms 209364 KB Output is correct
9 Correct 166 ms 209300 KB Output is correct
10 Correct 153 ms 209296 KB Output is correct
11 Correct 149 ms 209372 KB Output is correct
12 Correct 152 ms 209388 KB Output is correct
13 Correct 171 ms 209476 KB Output is correct
14 Correct 152 ms 209332 KB Output is correct
15 Correct 153 ms 209304 KB Output is correct
16 Correct 146 ms 209252 KB Output is correct
17 Correct 149 ms 209356 KB Output is correct
18 Correct 163 ms 209248 KB Output is correct
19 Correct 148 ms 209348 KB Output is correct
20 Correct 155 ms 209360 KB Output is correct
21 Correct 153 ms 209388 KB Output is correct
22 Correct 145 ms 209296 KB Output is correct
23 Correct 158 ms 209316 KB Output is correct
24 Correct 152 ms 209372 KB Output is correct
25 Correct 154 ms 209268 KB Output is correct
26 Correct 155 ms 209372 KB Output is correct
27 Correct 214 ms 209476 KB Output is correct
28 Correct 226 ms 209564 KB Output is correct
29 Correct 226 ms 209476 KB Output is correct
30 Correct 192 ms 209528 KB Output is correct
31 Correct 159 ms 209348 KB Output is correct
32 Correct 140 ms 209340 KB Output is correct
33 Correct 159 ms 209332 KB Output is correct
34 Correct 173 ms 209476 KB Output is correct
35 Correct 176 ms 209420 KB Output is correct
36 Correct 282 ms 209476 KB Output is correct
37 Correct 273 ms 209644 KB Output is correct
38 Correct 328 ms 209536 KB Output is correct
39 Correct 308 ms 209648 KB Output is correct
40 Correct 160 ms 209444 KB Output is correct
41 Correct 186 ms 209432 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 209360 KB Output is correct
2 Correct 162 ms 209364 KB Output is correct
3 Correct 145 ms 209284 KB Output is correct
4 Correct 163 ms 209368 KB Output is correct
5 Correct 154 ms 209340 KB Output is correct
6 Correct 184 ms 209372 KB Output is correct
7 Correct 146 ms 209288 KB Output is correct
8 Correct 176 ms 209364 KB Output is correct
9 Correct 166 ms 209300 KB Output is correct
10 Execution timed out 3051 ms 228020 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 209360 KB Output is correct
2 Correct 162 ms 209364 KB Output is correct
3 Correct 145 ms 209284 KB Output is correct
4 Correct 163 ms 209368 KB Output is correct
5 Correct 154 ms 209340 KB Output is correct
6 Correct 184 ms 209372 KB Output is correct
7 Correct 146 ms 209288 KB Output is correct
8 Correct 176 ms 209364 KB Output is correct
9 Correct 166 ms 209300 KB Output is correct
10 Correct 153 ms 209296 KB Output is correct
11 Correct 149 ms 209372 KB Output is correct
12 Correct 152 ms 209388 KB Output is correct
13 Correct 171 ms 209476 KB Output is correct
14 Correct 152 ms 209332 KB Output is correct
15 Correct 153 ms 209304 KB Output is correct
16 Correct 146 ms 209252 KB Output is correct
17 Correct 149 ms 209356 KB Output is correct
18 Correct 163 ms 209248 KB Output is correct
19 Correct 148 ms 209348 KB Output is correct
20 Correct 155 ms 209360 KB Output is correct
21 Correct 153 ms 209388 KB Output is correct
22 Correct 145 ms 209296 KB Output is correct
23 Correct 158 ms 209316 KB Output is correct
24 Correct 152 ms 209372 KB Output is correct
25 Correct 154 ms 209268 KB Output is correct
26 Correct 155 ms 209372 KB Output is correct
27 Correct 214 ms 209476 KB Output is correct
28 Correct 226 ms 209564 KB Output is correct
29 Correct 226 ms 209476 KB Output is correct
30 Correct 192 ms 209528 KB Output is correct
31 Correct 159 ms 209348 KB Output is correct
32 Correct 140 ms 209340 KB Output is correct
33 Correct 159 ms 209332 KB Output is correct
34 Correct 173 ms 209476 KB Output is correct
35 Correct 176 ms 209420 KB Output is correct
36 Correct 282 ms 209476 KB Output is correct
37 Correct 273 ms 209644 KB Output is correct
38 Correct 328 ms 209536 KB Output is correct
39 Correct 308 ms 209648 KB Output is correct
40 Correct 160 ms 209444 KB Output is correct
41 Correct 186 ms 209432 KB Output is correct
42 Execution timed out 3051 ms 228020 KB Time limit exceeded
43 Halted 0 ms 0 KB -