oj.uz

Submission #232788

# Submission time Handle Problem Language Result Execution time Memory
232788 2020-05-18T06:14:03 Z infinite_iq Ili (COI17_ili) C++14
100 / 100
 429 ms 1532 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 270
//#define mp make_pair
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll inf=1e18;
const ll mod=1e9+7;
const ld pai=acos(-1);
int N , M ;
string Ans ;
vi V [20009] ;
int Val ( string X ) {
        int Crnt = 0 ;
        for ( int i = 1 ; i < X .size() ; i ++ ) {
                Crnt *= 10 ;
                Crnt += X [i] - '0' ;
        }
        Crnt += ( X [0] == 'c' ? N : 0 ) ;
        return Crnt - 1 ;
}
int Done [20009] , Ret [20009] , Init [20009] ;
void Dfs ( int Node ) {
        if ( Done [Node] ) return ;
        Done [Node] = 1 ;
        for ( auto  U : V [Node] ) Dfs ( U ) ;
}
void Build () {
        for ( int i = 0 ; i < N ; i ++ ) Ret [i] = 1 - Done [i] ;
        for ( int i = N ; i < M + N ; i ++ ) {
                Ret [i] = 0 ;
                for ( auto U : V [i] ) Ret [i] |= Ret [U] ;
        }
}
int main () {
        cin >> N >> M >> Ans ;
        for ( int i = N ; i < N + M ; i ++ ) {
                string A , B ;
                cin >> A >> B ;
                V [i] .pb ( Val ( A ) ) ;
                V [i] .pb ( Val ( B ) ) ;
        }
        for ( int i = 0 ; i < M ; i ++ ) {
                if ( Ans [i] == '0' && !Done [i+N] ) {
                        Dfs ( i + N ) ;
                }
        }
        Build () ;
        for ( int i = 0 ; i < N + M ; i ++ ) {
                Init [i] = 1 - Ret [i] ;
        }
        for ( int i = N ; i < N + M ; i ++ ) {
                if ( Ret [i] == 0 ) {
                        Ans [i-N] = '0' ;
                }
        }
        for ( int i = 0 ; i < M ; i ++ ) {
                if ( Ans [i] != '?' ) C ;
                for ( int j = 0 ; j < N + M ; j ++ ) Done [j] = Init [j] ;
                Dfs ( i + N ) ;
                Build () ;
                for ( int j = 0 ; j < M ; j ++ ) {
                        if ( Ans [j] == '1' && Ret [j+N] != 1 ) {
                                Ans [i] = '1' ;
                                break ;
                        }
                }
        }
        cout << Ans << endl ;
}

Compilation message

ili.cpp: In function 'int Val(std::__cxx11::string)':
ili.cpp:37:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int i = 1 ; i < X .size() ; i ++ ) {
                           ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 6 ms 768 KB Output is correct
11 Correct 6 ms 896 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 6 ms 896 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 6 ms 768 KB Output is correct
11 Correct 6 ms 896 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 6 ms 896 KB Output is correct
15 Correct 72 ms 1152 KB Output is correct
16 Correct 169 ms 1272 KB Output is correct
17 Correct 139 ms 1280 KB Output is correct
18 Correct 368 ms 1408 KB Output is correct
19 Correct 139 ms 1272 KB Output is correct
20 Correct 346 ms 1528 KB Output is correct
21 Correct 429 ms 1496 KB Output is correct
22 Correct 317 ms 1532 KB Output is correct
23 Correct 357 ms 1408 KB Output is correct
24 Correct 349 ms 1528 KB Output is correct
25 Correct 240 ms 1528 KB Output is correct
26 Correct 249 ms 1528 KB Output is correct
27 Correct 238 ms 1528 KB Output is correct
28 Correct 217 ms 1408 KB Output is correct
29 Correct 233 ms 1528 KB Output is correct
30 Correct 229 ms 1528 KB Output is correct
31 Correct 296 ms 1408 KB Output is correct
32 Correct 370 ms 1528 KB Output is correct