oj.uz

Submission #80193

# Submission time Handle Problem Language Result Execution time Memory
80193 2018-10-19T13:47:45 Z fabjanm KOVANICE (COI15_kovanice) C++
10 / 100
 2000 ms 22652 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#include<cstring>

using namespace std;

int n,m,v;
int brcv=0;

vector<pair<int,int> >jed;
vector<pair<pair<int,int>,char> >raz;

int mapa[300050];

int parent[300500];
vector<int> sus[300500];

int sol[300500];
vector<int>koji;

bool uz[300500];
vector<int>koj;

void input(){
    cin>>n>>m>>v;
    int br1,br2;
    char zn;

    for(int i=0;i<v;i++){
        cin>>br1>>zn>>br2;
        if(zn=='=')jed.push_back(make_pair(min(br1,br2),max(br1,br2)));
        else raz.push_back(make_pair(make_pair(br1,br2),zn));
    }
}

void rek(int cvor, int br){
    bool soll=0;
    //cout<<cvor<<" "<<pros<<endl;
    if(br==n){
        sol[cvor]=1;
        uz[cvor]=true;
        koj.push_back(cvor);
        //return 1;
        return;
    }
    else if(sus[cvor].size()==0)return;
    for(int i=0;i<sus[cvor].size();i++) rek(sus[cvor][i], br+1);
    //cout<<cvor<<endl;
    if(koj.size()>0 && uz[koj.front()]){
        sol[cvor]=n-br+1;
        uz[cvor]=true;
        koj.push_back(cvor);
    }
    //return soll;
}

void solve(){
    sort(jed.begin(),jed.end());
    int oz=0;
    for(int i=0;i<jed.size();i++){
        int br1=jed[i].first;
        int br2=jed[i].second;
        if(mapa[br1]==0 && mapa[br2]==0){
            oz++;
            brcv++;
            mapa[br1]=oz;
            mapa[br2]=oz;
        }
        else if(mapa[br1]==0 && mapa[br2]!=0)mapa[br1]=mapa[br2];
        else if(mapa[br1]!=0 && mapa[br2]==0)mapa[br2]=mapa[br1];
    }

    for(int i=0;i<raz.size();i++){
        int br1=raz[i].first.first;
        int br2=raz[i].first.second;
        char zn=raz[i].second;

        if(mapa[br1]==0){
            oz++;
            brcv++;
            mapa[br1]=oz;
        }
        if(mapa[br2]==0){
            oz++;
            brcv++;
            mapa[br2]=oz;
        }

        if(zn=='<'){
            parent[mapa[br1]]=mapa[br2];
            sus[mapa[br2]].push_back(mapa[br1]);
        }
        else{
            parent[mapa[br2]]=mapa[br1];
            sus[mapa[br1]].push_back(mapa[br2]);
        }
    }
    /*cout<<endl;
    for(int i=1;i<=m;i++)cout<<i<<" -----> "<<mapa[i]<<endl;
    cout<<endl;*/

    /*for(int i=1;i<=brcv;i++){
        cout<<i<<" -> ";
        for(int j=0;j<sus[i].size();j++)cout<<sus[i][j]<<" ";
        cout<<endl;
    }

    cout<<11111111111<<"    "<<sol[4]<<endl;*/

    for(int i=1;i<=brcv;i++){
        int cvor=i;
        //cout<<cvor<<"    "<<parent[cvor]<<endl;
        if(parent[cvor]==0){
            //cout<<cvor<<endl;
            //cout<<cvor<<endl;
            rek(cvor, 1);
            //cout<<bl;
        }
    }
}

void print(){
    //cout<<endl;
    for(int i=1;i<=m;i++){
        if(sol[mapa[i]] != 0)cout<<"K"<<sol[mapa[i]]<<endl;
        else cout<<"?"<<endl;
    }
}

int main(){
    input();
    solve();
    print();



    return 0;
}

Compilation message

kovanice.cpp: In function 'void rek(int, int)':
kovanice.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sus[cvor].size();i++) rek(sus[cvor][i], br+1);
                 ~^~~~~~~~~~~~~~~~~
kovanice.cpp:43:10: warning: unused variable 'soll' [-Wunused-variable]
     bool soll=0;
          ^~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<jed.size();i++){
                 ~^~~~~~~~~~~
kovanice.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<raz.size();i++){
                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 11 ms 7556 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 14084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 14084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 22652 KB Time limit exceeded
2 Halted 0 ms 0 KB -