oj.uz

Submission #150944

# Submission time Handle Problem Language Result Execution time Memory
150944 2019-09-01T12:31:36 Z PedroBigMan Zamjena (COCI18_zamjena) C++14
70 / 70
 146 ms 10336 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF ((ll) pow(2,63) -1)
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
vector<ll> rnd;

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; vector<bool> visited;
    Graph(ll vertex) 
    {
        N=vertex; REP(i,0,N) {visited.pb(false);}
        vector<ll> useless; REP(i,0,N) {adj.pb(useless);}
    }
    
    vector<vector<ll> > CC()
    {
        vector<vector<ll> > ans;
        ll fi=-1; ll cnt=0;
        while(cnt<N)
        {
            rnd.clear();
            REP(i,fi+1,N) {if(!visited[i]) {fi=i; break;}}
            DFS(fi);
            ans.pb(rnd); cnt+=rnd.size();
        }
        return ans;
    }
    
    void DFS(ll s)
    {
        visited[s]=true;
        rnd.pb(s);
        REP(i,0,adj[s].size()) 
        {
            if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
        }
        return;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N; cin>>N; vector<pl> a; vector<pl> b;
    string s; bool isint; ll cur; map<string,ll> code;
    ll al=0;
    REP(i,0,N) 
    {
        cin>>s; isint=true;
        cur=0;
        REP(j,0,s.size()) 
        {
            if((((ll) s[j]) < 48) || (((ll) s[j]) > 57)) {isint=false;}
            cur+=(pow(10,s.size()-j-1))*(((ll) s[j]) - 48);
        }
        if(isint) {a.pb(mp(1,cur));}
        else 
        {
            if(code.count(s)>0) {a.pb(mp(0,code[s]));}
            else {code[s]=al; al++; a.pb(mp(0,code.size()-1));}
        }
    }
    REP(i,0,N) 
    {
        cin>>s; isint=true;
        cur=0;
        REP(j,0,s.size()) 
        {
            if((((ll) s[j]) < 48) || (((ll) s[j]) > 57)) {isint=false;}
            cur+=(pow(10,s.size()-j-1))*(((ll) s[j]) - 48);
        }
        if(isint) {b.pb(mp(1,cur));}
        else 
        {
            if(code.count(s)>0) {b.pb(mp(0,code[s]));}
            else {code[s]=al; al++; b.pb(mp(0,code.size()-1));}
        }
    }
    
    Graph G(code.size());
    REP(i,0,N)
    {
        if(a[i].ff==0 && b[i].ff==0 && a[i].ss!=b[i].ss) {G.adj[a[i].ss].pb(b[i].ss); G.adj[b[i].ss].pb(a[i].ss);}
    }
    vector<ll> ass; REP(i,0,code.size()) {ass.pb(i);}
    vector<vector<ll> > Con = G.CC(); ll fe; 
    REP(i,0,Con.size())
    {
        fe=Con[i][0];
        REP(j,0,Con[i].size()) {ass[Con[i][j]]=fe;}
    }
    
    vector<ll> val; REP(i,0,code.size()) {val.pb(-1);}
    ll ind;
    
    REP(i,0,N)
    {
        if(a[i].ff==0 && b[i].ff==1)
        {
            ind = ass[a[i].ss];
            if(val[ind]==-1) {val[ind]=b[i].ss;}
            else if(val[ind]!=b[i].ss) {cout<<"NE"<<endl; return 0;}
        }
        else if(a[i].ff==1 && b[i].ff==0)
        {
            ind = ass[b[i].ss];
            if(val[ind]==-1) {val[ind]=a[i].ss;}
            else if(val[ind]!=a[i].ss) {cout<<"NE"<<endl; return 0;}
        }
        else if(a[i].ff==1 && b[i].ff==1) {if(a[i].ss!=b[i].ss) {cout<<"NE"<<endl; return 0;}}
    }
    cout<<"DA"<<endl;
    return 0;
}

Compilation message

zamjena.cpp: In function 'void Out(std::vector<long long int>)':
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:20:29:
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                             ~~~~~~~~~~~~
zamjena.cpp:20:25: note: in expansion of macro 'REP'
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                         ^~~
zamjena.cpp: In member function 'void Graph::DFS(ll)':
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:52:13:
         REP(i,0,adj[s].size()) 
             ~~~~~~~~~~~~~~~~~    
zamjena.cpp:52:9: note: in expansion of macro 'REP'
         REP(i,0,adj[s].size()) 
         ^~~
zamjena.cpp: In function 'int main()':
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:71:13:
         REP(j,0,s.size()) 
             ~~~~~~~~~~~~         
zamjena.cpp:71:9: note: in expansion of macro 'REP'
         REP(j,0,s.size()) 
         ^~~
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:87:13:
         REP(j,0,s.size()) 
             ~~~~~~~~~~~~         
zamjena.cpp:87:9: note: in expansion of macro 'REP'
         REP(j,0,s.size()) 
         ^~~
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:105:25:
     vector<ll> ass; REP(i,0,code.size()) {ass.pb(i);}
                         ~~~~~~~~~~~~~~~
zamjena.cpp:105:21: note: in expansion of macro 'REP'
     vector<ll> ass; REP(i,0,code.size()) {ass.pb(i);}
                     ^~~
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:107:9:
     REP(i,0,Con.size())
         ~~~~~~~~~~~~~~           
zamjena.cpp:107:5: note: in expansion of macro 'REP'
     REP(i,0,Con.size())
     ^~~
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:110:13:
         REP(j,0,Con[i].size()) {ass[Con[i][j]]=fe;}
             ~~~~~~~~~~~~~~~~~    
zamjena.cpp:110:9: note: in expansion of macro 'REP'
         REP(j,0,Con[i].size()) {ass[Con[i][j]]=fe;}
         ^~~
zamjena.cpp:11:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
zamjena.cpp:113:25:
     vector<ll> val; REP(i,0,code.size()) {val.pb(-1);}
                         ~~~~~~~~~~~~~~~
zamjena.cpp:113:21: note: in expansion of macro 'REP'
     vector<ll> val; REP(i,0,code.size()) {val.pb(-1);}
                     ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 6 ms 760 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1912 KB Output is correct
2 Correct 36 ms 3568 KB Output is correct
3 Correct 63 ms 5868 KB Output is correct
4 Correct 76 ms 6632 KB Output is correct
5 Correct 146 ms 10336 KB Output is correct
6 Correct 93 ms 6620 KB Output is correct