oj.uz

답안 #43651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43651 2018-03-19T07:00:36 Z smu201111192 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 54 ms 55336 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;
        }
        step++;
    }
    return ret;
}
void dfsAll(int n){
    memset(disCovered,-1,sizeof(disCovered));
    for(int i=0; i < 2 * n;i++)
        if(disCovered[i]==-1)
            dfs(i);
}
//void answer(int cnt){
//    cout<<cnt<<endl;
//}
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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 55336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 55336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 55336 KB Output isn't correct
2 Halted 0 ms 0 KB -