oj.uz

답안 #43657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43657 2018-03-19T07:16:01 Z smu201111192 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
69 / 100
 5000 ms 92976 KB 
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 500005;
vector<pair<int,int>> temp[MAXN];
vector<int> adj[MAXN],rev[MAXN];
int dist[MAXN][2],disCovered[MAXN],step = 0,sccId[MAXN],sccNumber = 0;
vector<int> group[MAXN];
int chk[MAXN];
int getV(int x,int y){
    if(temp[y].size() > 1 && temp[y][0].second == x) return 2 * y + 1;
    return 2 * y;
}
void addEdge(int u,int v){
    adj[u].push_back(v);
    rev[v].push_back(u);
}
void bfs(int root){
    queue<int> q;
    for(int i=0;i<MAXN;i++)for(int j=0;j<2;j++) dist[i][j] = -1;
    dist[root*2][0] = 0;
    q.push(root*2);
    while(!q.empty()){
        int here = q.front(); q.pop();
        for(auto x:rev[here]){
            if(dist[x][0] == -1){ dist[x][0] = dist[here][0] + 1; q.push(x); }
        }
    }
    dist[root*2+1][1] = 0;
    q.push(root*2+1);
    while(!q.empty()){
        int here = q.front(); q.pop();
        for(auto x:rev[here]){
            if(dist[x][1] == -1){ dist[x][1] = dist[here][1] + 1; q.push(x); }
        }
    }
}
stack<int> st;
int dfs(int here){
    int there;
    st.push(here);
    disCovered[here]=step++;
    int ret=disCovered[here];
    for(int i=0;i<adj[here].size();i++){
        there=adj[here][i];
        if(disCovered[there]==-1)
            ret=min(dfs(there),ret);
        else if(sccId[there]==-1)
            ret=min(ret,disCovered[there]);
    }
    if(ret==disCovered[here]){
        while(true){
            int num=st.top();st.pop();
            group[sccNumber].push_back(num);
            sccId[num]=sccNumber;
            if(num==here)
                break;
        }
        sccNumber++;
    }
    return ret;
}
void dfsAll(int n){
    memset(disCovered,-1,sizeof(disCovered));
    memset(sccId,-1,sizeof(sccId));
    for(int i=0; i < 2 * n;i++)
        if(disCovered[i]==-1)
            dfs(i);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    
    for(int i=0;i<M;i++){
        temp[R[i][0]].push_back({i,R[i][1]});
        temp[R[i][1]].push_back({i,R[i][0]});
    }
    for(int i=0;i<N;i++){
        sort(temp[i].begin(),temp[i].end());
    }
    for(int here=0;here<N;here++){
        if(temp[here].size() == 0) continue;
        int there = temp[here][0].second;
        addEdge(2*here,getV(here,there));
        there = (temp[here].size() > 1 ? temp[here][1].second : temp[here][0].second );
        addEdge(2*here+1,getV(here,there));
    }
    dfsAll(N);
    bfs(P);
    for(int k=0;k<Q;k++){
        int cnt = 0;
        memset(chk,0,sizeof(chk));
        for(int i=0;i<N;i++){
            int bit = G[k];
            if(dist[i*2][0] == -1 || dist[i*2][0] > bit) continue;
            bit -= dist[i*2][0];
            if(bit == 0) chk[i] = 1;
            int id = sccId[2*P];
            if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
                chk[i] = 1;
            }
        }
        for(int i=0;i<N;i++){
            int bit = G[k];
            if(dist[i*2][1] == -1 || dist[i*2][1] > bit) continue;
            bit -= dist[i*2][1];
            if(bit == 0) chk[i] = 1;
            int id = sccId[2*P+1];
            if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
                chk[i] = 1;
            }
        }
        for(int i=0;i<N;i++) cnt += chk[i];
        answer(cnt);
    }
}

Compilation message

garden.cpp: In function 'int dfs(int)':
garden.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[here].size();i++){
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 57328 KB Output is correct
2 Correct 56 ms 57308 KB Output is correct
3 Correct 55 ms 57448 KB Output is correct
4 Correct 55 ms 57052 KB Output is correct
5 Correct 55 ms 57080 KB Output is correct
6 Correct 58 ms 57404 KB Output is correct
7 Correct 56 ms 57080 KB Output is correct
8 Correct 60 ms 57268 KB Output is correct
9 Correct 58 ms 57464 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 57328 KB Output is correct
2 Correct 56 ms 57308 KB Output is correct
3 Correct 55 ms 57448 KB Output is correct
4 Correct 55 ms 57052 KB Output is correct
5 Correct 55 ms 57080 KB Output is correct
6 Correct 58 ms 57404 KB Output is correct
7 Correct 56 ms 57080 KB Output is correct
8 Correct 60 ms 57268 KB Output is correct
9 Correct 58 ms 57464 KB Output is correct
10 Correct 65 ms 57156 KB Output is correct
11 Correct 118 ms 61452 KB Output is correct
12 Correct 165 ms 65180 KB Output is correct
13 Correct 161 ms 83076 KB Output is correct
14 Correct 349 ms 84948 KB Output is correct
15 Correct 394 ms 85344 KB Output is correct
16 Correct 303 ms 77376 KB Output is correct
17 Correct 273 ms 74768 KB Output is correct
18 Correct 121 ms 65288 KB Output is correct
19 Correct 344 ms 84896 KB Output is correct
20 Correct 400 ms 85344 KB Output is correct
21 Correct 311 ms 77192 KB Output is correct
22 Correct 279 ms 74680 KB Output is correct
23 Correct 434 ms 87372 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 57328 KB Output is correct
2 Correct 56 ms 57308 KB Output is correct
3 Correct 55 ms 57448 KB Output is correct
4 Correct 55 ms 57052 KB Output is correct
5 Correct 55 ms 57080 KB Output is correct
6 Correct 58 ms 57404 KB Output is correct
7 Correct 56 ms 57080 KB Output is correct
8 Correct 60 ms 57268 KB Output is correct
9 Correct 58 ms 57464 KB Output is correct
10 Correct 65 ms 57156 KB Output is correct
11 Correct 118 ms 61452 KB Output is correct
12 Correct 165 ms 65180 KB Output is correct
13 Correct 161 ms 83076 KB Output is correct
14 Correct 349 ms 84948 KB Output is correct
15 Correct 394 ms 85344 KB Output is correct
16 Correct 303 ms 77376 KB Output is correct
17 Correct 273 ms 74768 KB Output is correct
18 Correct 121 ms 65288 KB Output is correct
19 Correct 344 ms 84896 KB Output is correct
20 Correct 400 ms 85344 KB Output is correct
21 Correct 311 ms 77192 KB Output is correct
22 Correct 279 ms 74680 KB Output is correct
23 Correct 434 ms 87372 KB Output is correct
24 Correct 259 ms 57156 KB Output is correct
25 Correct 447 ms 61644 KB Output is correct
26 Correct 545 ms 65272 KB Output is correct
27 Correct 2243 ms 83148 KB Output is correct
28 Correct 2206 ms 85268 KB Output is correct
29 Correct 3170 ms 85396 KB Output is correct
30 Correct 1857 ms 77172 KB Output is correct
31 Correct 1669 ms 74772 KB Output is correct
32 Correct 584 ms 65224 KB Output is correct
33 Correct 2305 ms 84876 KB Output is correct
34 Correct 3075 ms 85388 KB Output is correct
35 Correct 1855 ms 77276 KB Output is correct
36 Correct 2338 ms 74712 KB Output is correct
37 Correct 1820 ms 87192 KB Output is correct
38 Execution timed out 5022 ms 92976 KB Time limit exceeded